algorithm - 在最多包含两个负边的图中查找最短路径距离

Question

我得到一个有向图，其中每条边都有一个成本。利用图中最多有两条负边的事实，我的目标是找到从给定节点 s 到所有节点的最短路径距离在V中。算法的时间复杂度应该是O(|E| + |V|*log|V|)，所以我想我需要应用Dijkstra的算法。

我猜想我需要以某种方式将给定的图转换为具有非负权重的新图，该图中从 s 到 v 的最短路径将等效于给定图中所需的最短路径。或也许我需要修改 Dijkstra 算法？

我现在很苦恼。任何帮助将不胜感激!

Answer 1

由于 Dijkstra 算法是贪婪的，因此不适用于负权重。您需要一些其他算法，例如 the Bellman-Ford Algorithm为此目的。

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

为此，您可以查看 Johnson 算法。约翰逊的算法包括以下步骤(取自 Wikipedia ):

1. 首先，一个新节点 q 被添加到图中，通过零权重边连接到每个其他节点。
2. 其次，使用 Bellman–Ford 算法，从新顶点 q 开始，为每个顶点 v 找到从 q 到 v 的路径的最小权重 h(v)。如果这一步检测到负循环，则算法终止。
3. 接下来使用 Bellman–Ford 算法计算的值对原始图的边重新加权:从 u 到 v 的边，长度为 w(u,v)，被赋予新的长度 w(u,v) + h(u) − h(v)。
4. 最后，删除 q，并使用 Dijkstra 算法在重新加权的图中找到从每个节点 s 到每个其他顶点的最短路径。