在至多包含两个负边的图中求最短路径距离

Question

给出了一个有向图，其中每个边都有一个cost.Taking优点，即图中最多有两个负边，我的目标是求出从给定节点到V中所有节点的最短路径距离。算法的时间复杂度应该是O(|E| + |V|*log|V|)，所以我认为需要应用Dijkstra算法。

我猜想我需要以某种方式将我给定的图转换成一个新的图，该图中从s到v的最短路径将等价于给定图中所需的最短路径。或者我需要修改Dijkstra的算法？

我现在很挣扎。任何帮助都将不胜感激！

Answer 1

由于Dijkstra的算法是贪婪的，所以它不能处理负重。为此，您需要一些其他算法(如Bellman算法 )。

但是，如果您仍然想使用Dijkstra的算法，有一个已知的方法。在这种方法中，您需要重新分配成本，以便所有的成本都变为正的。

为此，您可以查看Johnson的算法。Johnson的算法包括以下步骤(取自维基百科)：

1. 首先，将一个新的节点q添加到图中，将零权边连接到其他每个节点。
2. 其次，使用Bellman算法，从新的顶点q开始，为每个顶点v求出从q到v的路径的最小权h(v)，如果这一步检测到负循环，则该算法被终止。
3. 然后用Bellman算法计算的值对原图的边进行重加权:给出了长度为w(u，v) + h(u)−h( v )的由u到v的边。
4. 最后，去掉Q，使用Dijkstra算法在重加权图中找到从每个节点到每个其他顶点的最短路径。

Answer 2

只是一些要开始的定义：

• 设负边为n1 = (n1s, n1e) (即从顶点n1s到顶点n1e)。 和n2 = (n2s, n2e)。
• 定义我们希望找到的最短路径的起始点和结束顶点，分别作为s和e。

的基本思想：

多次运行Dijkstra算法，以负重边的每个顶点和每个端点的顶点作为起点，以负重边的端顶点和每个起始顶点作为结束点，并利用这些值找到实际的最短路径。

算法：

• 使用Dijkstra的算法确定以下最短路径，所有这些都不包括两个负边： S=s -> e //最短路径从s到e sn1 =s -> n1s //最短路径从s到n1 sn2 =s -> n2s //最短路径从s到n2 ne1 = n1e -> e/最短路径从n1到e n1n2 = n1e -> n2s /最短路径从n1e到n1e 19#=en21#e//从n2到e n2n1 = n2e -> n1s // n2到n1的最短路径
• 现在只需计算以下的最小值： se // s至e sn1 + n1 + ne1 // s to n1 to e sn2 + n2 + ne2 /s to n2 to e sn1 + n1 + n1n2 + n2 + ne2 /s to n1 to n2 to e sn2 + n2 + n2 ++en19#/s to to to e

因为Dijkstra的算法连续7次运行，

运行时间为O(7(|E| + |V| log |V|)) = O(|E| + |V| log |V|)。