最佳的最短路径算法

Question

弗洛伊德-沃尔沙算法和迪杰斯特拉算法有什么区别，哪个更适合在图中找到最短路径?

我需要计算网络中所有节点对之间的最短路径，并将结果保存到数组中，如下所示:

**A     B     C     D      E**
A 0     10    15    5     20
B 10     0    5     5     10
C 15     5    0     10    15
D 5      5    10    0     15
E 20     10    15   15    0

- Ricardo Rod

---

但另一个问题已经关闭了，主要是因为用户的英语不好，而且其中一个解决方案将这两个算法作为备选方案之一。如果我们将其标记为重复问题，那么作者如何了解先前问题的更多信息呢？我们真的都会很友善地去那里投票重新打开吗？ - Will

抱歉，我想添加一个关于数组的示例，但我没有做。 - Ricardo Rod

感谢SilentGhost重新编辑我的问题。 - Ricardo Rod

那个图表里的 DE 应该不是15吗？ - Daniel Roseman

Answer 1

Dijkstra算法 可以找到一张图中一个节点到其他每个节点的最短路径。需要对每个节点运行该算法，权值必须为非负数，如果有必要，需要先对图中的值进行规范化。

Floyd-Warshall算法可以在单次运行中计算所有节点之间的最短路径! 循环权重必须为非负数，并且该图必须是 有向的 （您的图表不是）。

Johnson算法使用Dijkstra算法在单次运行中查找所有配对，并适用于稀疏树（请参阅分析链接）。

- Will

---

从您引用的Dijkstra维基百科链接中可以看到：“该算法找到该顶点与每个其他顶点之间成本最低的路径”（我强调了“每个”）。因此，您不需要为每对顶点运行它，而只需要为每个顶点运行一次即可。 - Andreas Brinck

可以通过将无向图中的每条边uv替换为两条带有相同权重的有向边(u,v)和(v,u)，来将无向图转换为有向图。那么使用Floyd-Warshall算法应该也能很好地处理这种情况吧？ - Nick Lewis

错误..弗洛伊德-沃舍尔算法不要求边缘为非负数，来自维基百科“是一种用于在带有正或负边权（但没有负循环）的加权图中查找最短路径的图形分析算法”。 - Jimmar

Answer 2

Floyd Warshall算法可以找到所有顶点之间的路径，但Dijkstra算法只能找到一个顶点到其他所有顶点之间的路径。

Floyd Warshall算法的时间复杂度为O(|V|³)，而Dijkstra算法的时间复杂度为O(|E| + |V| log |V|)，但你需要运行V次才能找到所有的路径，这将导致时间复杂度为O(|E * V| + |V²| log |V|)。我猜想这意味着重复使用Dijkstra算法可能比FW算法更快，建议尝试两种方法并查看实际情况哪种更快。

- Andreas Brinck

---

Francis Haart的评论：“@Andreas Brinck，在完全图中，E=（V^2-V）/2，并且迪杰斯特拉算法不会更快。” - Peter O.

Answer 3

Dijkstra算法只能找到从一个顶点出发的最短路径，而Floyd-Warshall算法可以找到所有顶点之间的最短路径。

- Gergely Orosz

Answer 4

如果你想找到所有顶点对之间的最短路径，可以使用Floyd-Warshall算法，因为它的运行时间比Dijkstra算法要长得多。

Floyd-Warshall算法的最坏情况性能为O(|V|³)，而Dijkstra算法的最坏情况性能为O(|E| + |V|log |V|)。

- Yacoby

Answer 5

与此同时，单源最短路径问题的更好算法已经被发现。一个实际相关的算法是Torben Hagerup推导Dijkstra算法。该算法具有与Djikstra相同的最坏情况复杂度，但在平均情况下，预期运行时间与图的大小成线性关系，比纯Dijkstra快得多。该算法的思想基于这样的想法，即没有必要总是从队列中轮询最小边缘。可以从队列中轮询一条边缘，其权重是最小边缘权重的1+k倍，其中k是大于0的某个数字。即使选择了这样的边缘，算法仍然会找到最短路径。

- SpaceTrucker

---

归档版本：https://web.archive.org/web/20180613142303/https://link.springer.com/chapter/10.1007%2F3-540-45022-X_7 - Peter Ritchie

Answer 6

我们不能直接比较“Floyd-Warshall”和“Dijkstra”算法，因为它们的用途略有不同。请参考下表以做出最佳选择。

算法	时间复杂度（大O表示法）	空间复杂度（大O表示法）	有向还是无向图？	处理循环图？	处理负边权重？	何时使用？
迪杰斯特拉算法	(E+V)LogV	V	两者皆可	否	否	从单个源点到所有顶点的最短路径
贝尔曼-福特算法	VE	V	两者皆可	不适用于负权重环	是	从单个源点到所有顶点的最短路径
拓扑排序算法	V+E	V	有向	否	是	从单个源点到所有顶点的最短路径
弗洛伊德-沃舍尔算法	V^3	V^2	两者皆可	不适用于负权重环	是	从所有顶点到所有顶点的最短路径

- Vipul Kumar

---

请不要在多个问题上发布相同的答案。 - undefined

Answer 7

Dijkstra算法主要用于单源最短路径查找，即从一个节点到所有其他节点的最短路径，而Floyd-Warshall算法用于全源最短路径，即所有顶点对之间的最短路径。Floyd-Warshall算法的最坏情况性能为O（|V|3），而Dijkstra的最坏情况性能为O（|E| + |V|log |V|）。 此外，Dijkstra算法不能用于负权重（我们使用Bellmann Ford算法来解决），但是对于Floyd-Warshall算法，我们可以使用负权重，但不能有负循环。

- piyush_raman