最佳最短路径算法

“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

来源

2009-12-04 ricardo

但另一个关闭，主要是因为用户的英语不好，而其中一个解决方案将这两个确切的算法命名为替代方案。如果我们将其视为dup，那么作者将如何更详细地了解上一个问题？我们真的都会很好，去那边投票重新开放吗？ – Will 2009-12-04 13:15:47

嗨，对不起，但想要添加一个图片的数组示例，但是我没有做 – ricardo 2009-12-04 13:17:47

谢谢，SilentGhost用于重新编辑我的问题 – ricardo 2009-12-04 13:20:27

Dijkstra的算法找到一个节点和图中每个其他节点之间的最短路径。你会为每个节点运行一次。权重必须是非负的，所以如果有必要，您必须首先对图中的值进行归一化。

Floyd-Warshall计算一次运行中所有节点对之间的最短路径！周期权重必须是非负的，并且图表必须是指示（您的图表不是）。

Johnson的算法使用Dijkstra算法在单遍中查找所有对，并且对于稀疏树（查看链接进行分析）更快。

来源

2009-12-04 13:22:37 Will

从您提到的Dijkstra的维基百科链接中找到：“该算法在该顶点和每个**其他顶点之间找到成本最低的路径”（我强调）。因此，您不需要为每对顶点运行它，而只需要为每个顶点运行它。 – 2009-12-04 13:43:00

thx Andreas，fixed – Will 2009-12-04 13:46:50

您可以通过用两个边（u，v）和（v，u）替换具有相同权重的每个边uv，将无向图转换为有向图。那么大概Floyd-Warshall应该工作得很好？ – 2009-12-04 13:50:29

弗洛伊德沃肖尔找到所有对点之间的路径，但Dijkstra算法只发现从一个顶点到所有其他顶点的路径。（V | ）和Dikstra是O（| E | + | V | log | V |），但是你必须运行它V次才能找到所有的对O的复杂性（| E * V | + | V | log | V |）我想。这意味着重复使用Dijsktra的速度可能比FW算法快，我会尝试两种方法，并在实际情况下查看哪种方法最快。

来源

2009-12-04 13:11:16

Francis Haart的评论：“@Andreas Brinck，在一个完整的图中，E =（V^2-V）/ 2，而dijkstra's不会更快。” – 2012-02-15 00:15:38

如果您想查找所有顶点对之间的最短路径，使用Floyd-Warshall算法，因为它的运行时间比Dijkstra的算法运行时间要长（远）。

的弗洛伊德 - Warshall算法为O的最坏情况下的性能（| V | ），其中作为Dijkstra的为O的糟糕情况下的性能（| E | + | V |登录| V |）

来源

2009-12-04 13:11:51 Yacoby

Dijkstra找到最短路径从一个顶点，Floyd-Warshall发现它在之间的所有其中。

来源

2009-12-04 13:13:53

Dijkstra's主要用于单对最短路径查找，即从一个节点到所有其他节点，其中Floyd-Warshall用于全对最短路径，即所有对顶点之间的最短路径。 Floyd-Warshall算法的最坏情况表现为O（| V | 3），其中Dijkstra的情况表现为O（| E | + | V | log | V |） Dijkstra's也不能用于负数重量（我们使用贝尔曼福特相同）。但是对于Floyd-Warshall，我们可以使用负权重但无负循环

来源

2012-07-11 08:09:31

在此期间，更好的单源最短路径问题算法是已知的。一个实际相关的是derivation of Dijkstra's algorithm by Torben Hagerup。该算法具有与Djikstra相同的最坏情况复杂度，但在平均情况下，期望的运行时间在图的大小上是线性的，这比纯粹的Dijkstra快得多。该算法的思想基于这样的想法，即不需要始终轮询队列中的最小边缘。有可能轮询队列中的边缘，其重量是最小边权重的1+k倍，其中k是某些数字更大的0。即使选择了这种边缘，该算法仍然会找到最短路径。

来源

2012-10-17 05:34:07 SpaceTrucker

最佳最短路径算法

回答

相关问题