最佳最短路径算法
“Floyd-Warshall 算法” 和 “Dijkstra 算法” 之间有什么区别，哪种算法最适合查找图中的最短路径？
我需要计算网络中所有对之间的最短路径并将结果保存到数组中，如下所示：
**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
What is the difference between the "Floyd-Warshall algorithm" and "Dijkstra's Algorithm", and which is the best for finding the shortest path in a graph?
I need to calculate the shortest path between all the pairs in a net and save the results to an array as follows:
**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
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
Dijkstra 的算法找到节点与图中每个其他节点之间的最短路径。您将为每个节点运行一次。权重必须为非负数，因此如有必要，您必须首先对图表中的值进行标准化。
Floyd-Warshall 计算单个节点中所有节点对之间的最短路径跑步！循环权重必须是非负的，并且图表必须是有向的（您的图表不是有向的）。
Johnson 算法使用 Dijkstra 算法一次查找所有对，对于稀疏树来说速度更快（请参阅分析链接）。
Dijkstra's algorithm finds the shortest path between a node and every other node in the graph. You'd run it once for every node. Weights must be non-negative, so if necessary you have to normalise the values in the graph first.
Floyd-Warshall calculates the shortest routes between all pairs of nodes in a single run! Cycle weights must be non-negative, and the graph must be directed (your diagram is not).
Johnson's algorithm is using Dijkstra's algorithm to find all pairs in a single pass, and is faster for sparse trees (see the link for analysis).
Floyd Warshall 找到所有顶点对之间的路径，但 Dijkstra 只能找到从一个顶点到所有其他顶点的路径。
Floyd Warshall 的时间复杂度为 O(|V|3)，Dikstra 的时间复杂度为 O(|E| + |V| log |V|)，但你必须运行 V 次才能找到所有给出的对我猜复杂度为 O(|E * V| + |V2| log |V|) 。这意味着重复使用 Dijsktra 可能比 FW 算法更快，我会尝试这两种方法，看看在实际情况下哪种方法最快。
Floyd Warshall find the paths between all pairs of vertices, but Dijkstra only finds the path from one vertex to all others.
Floyd Warshall is O(|V|3) and Dikstra is O(|E| + |V| log |V|) but you'll have to run it V times to find all pairs which gives a complexity of O(|E * V| + |V2| log |V|) I guess. This means it's possibly faster to use Dijsktra repeatedly than the FW algorithm, I would try both approaches and see which one is fastest in the actual case.
Dijkstra 仅从一个顶点找到最短路径，Floyd-Warshall 则在所有顶点之间找到最短路径。
Dijkstra finds the shortest path from only one vertex, Floyd-Warshall finds it between all of them.
如果您想找到所有顶点对之间的最短路径，请使用 Floyd-Warshall 算法，因为它的运行时间比 Dijkstra 算法（远）长。
Floyd-Warshall 算法的最坏情况性能为 O(|V|3)，而 Dijkstra 算法的最坏情况性能为 O(|E| + |V|log |V|)
Use the Floyd-Warshall algorithm if you want to find the shortest path between all pairs of vertexes, as it has a (far) higher running time than Dijkstra's algorithm.
The Floyd-Warshall algorithm has a worst case performance of O(|V|3), where as Dijkstra's has a worse case performance of O(|E| + |V|log |V|)
同时，针对单源最短路径问题的更好算法是已知的。实际相关的是 Torben Hagerup 对 Dijkstra 算法的推导。该算法具有与 Djikstra 相同的最坏情况复杂度，但在平均情况下，预期运行时间与图的大小呈线性关系，这比纯 Dijkstra 快得多。该算法的思想基于这样的思想：不需要总是从队列中轮询最小边。可以从队列中轮询一条边，其权重是最小边权重的
1+k倍，其中k是大于0< /代码>。即使选择了这样的边，算法仍然会找到最短路径。In the meanwhile better algorithms for the single source shortest path problem are known. A practically relevant one is a derivation of Dijkstra's algorithm by Torben Hagerup. The algorithm has the same worst case complexity as Djikstra's, but in the average case the expected runtime is linear in the size of the graph, which is much faster than the pure Dijkstra. The idea of the algorithm is based on the idea, that there is no need to always poll the minimum edge from the queue. It is possible poll an edge from the queue, whose weight is
1+ktimes as large as the minimum edge weight, wherekis some number larger0. Even if such an edge is chosen, the algorithm will still find the shortest path.Dijkstra 主要用于单对最短路径查找，即从一个节点到所有其他节点，而 Floyd-Warshall 则用于全对最短路径，即所有顶点对之间的最短路径。 Floyd-Warshall 算法的最坏情况性能为 O(|V|3)，而 Dijkstra 算法的最坏情况性能为 O(|E| + |V|log |V|)
此外，Dijkstra 不能用于负权重（我们使用 Bellmann Ford 进行同样的操作）。但对于 Floyd-Warshall，我们可以使用负权重，但不能使用负循环
Dijkstra's is mainly for single pair shortest path finding i.e. from one node to all other nodes, where as Floyd-Warshall is for all-pair shortest path i.e. shortest path between all pair of vertices. The Floyd-Warshall algorithm has a worst case performance of O(|V|3), where as Dijkstra's has a worse case performance of O(|E| + |V|log |V|)
Also Dijkstra's cannot be used for negative weights ( we use Bellmann Ford for the same ). but for Floyd-Warshall we can use negative weights but no negative cycles
我们不能直接比较“Floyd-Warshall”和“Dijkstra”算法，因为两者的用途略有不同。请参考下表做出最佳选择。
We can't directly compare "Floyd-Warshall" and "Dijkstra" algorithms as both serve a little different purpose. Please refer the table below to make the best choice.