最佳最短路径算法 [英] The best shortest path algorithm

问题描述

Floyd-Warshall算法 和 Dijkstra算法 之间的区别是什么？找到图中最短路径的最佳方法是什么？ / p>

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

  ** ABCDE ** 
 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 
  

解决方案

Dijkstra 的算法可找到节点与每个节点之间的最短路径图中的其他节点。您将为每个节点运行一次。权重必须为非负数，因此，如有必要，您必须首先对图形中的值进行标准化。

Floyd-Warshall 可在一次运行中计算所有成对节点之间的最短路径！循环权重必须为非负数，并且图形必须为有向（您的图形不是）。

Johnson 的算法正在使用Dijkstra的算法一次找到所有对，而对于稀疏树则更快（请参阅分析链接。）

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

解决方案

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).

这篇关于最佳最短路径算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！