algorithm - 加权有向图中的最短路径

Question

我需要在加权有向图中找到两个节点 s,t 之间的最短路径。以下是限制:

1. 权重可以是负数。
2. 这条路径必须经过一条特定的边让我们称她为 e 并且她从节点 u 到 v。
3. 输出路径必须简单，即我们只经过一个节点一次。

现在我有一个解决方案的想法，但我不知道输出是否是一条简单的路径。

我的解决方案是运行 bellman ford 算法两次，一次从 s，第二次从 v。最短路径将是 s 到 u，u 到 v，v 到 t。

因为我希望它简单，所以我不会使用我已经在第二次 bellman ford run 中使用的节点。

因为我希望它是最短的，所以我将检查在从 s 运行到 u 之前从 v 运行 bellman ford 到 t 是否比其他方式更快(如果有一个节点都使用哪里是放置它的最佳位置).

感谢各位 helper !

Answer 1

即使找到这样的路径也是 NP 完全的。这是因为两个顶点/边缘不相交的路径问题是有向图中的 NPC。假设边 e=(u,v) 那么您正在寻找 (s,u), (v,t) 不相交的路径，但这在有向图中是 NP 完全的。

在这里您可以找到硬度结果: https://www.sciencedirect.com/science/article/pii/0304397580900092

您当前基于 Bellman-ford 的算法并不能为所有情况给出正确答案(它可能无法在有路径的情况下找到路径)，但是，它可能是一个很好的启发式方法。如果你的图是无向的，那么任务就容易多了。

如果您允许重复顶点，那么任何最短路径算法都是正确的方法。