最佳最短路徑算法

「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

最佳最短路徑算法

回答

相關問題