Floyd-Warshall演算法

Floyd-Warshall演算法(英語:Floyd-Warshall algorithm),中文亦稱弗洛伊德演算法佛洛依德演算法[1],是解決任意兩點間的最短路徑的一種演算法[2],可以正確處理有向圖或負權(但不可存在負權迴路)的最短路徑問題,同時也被用於計算有向圖的遞移閉包[3]

Floyd-Warshall演算法
概況
類別全域最短路徑問題(適用於帶權圖)
資料結構
複雜度
平均時間複雜度
最壞時間複雜度
最佳時間複雜度
空間複雜度
相關變數的定義
點集

Floyd-Warshall演算法的時間複雜度[4]空間複雜度,其中是點集。

原理

Floyd-Warshall演算法的原理是動態規劃[5]

 為從  的只以 集合中的節點為中間節點的最短路徑的長度。

  1. 若最短路徑經過點k,則 
  2. 若最短路徑不經過點k,則 

因此, 

在實際演算法中,為了節約空間,可以直接在原來空間上進行迭代,這樣空間可降至二維。

演算法描述

Floyd-Warshall演算法的虛擬碼描述如下:

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

其中dist[i][j]表示由點 到點 的代價,當其為 ∞ 表示兩點之間沒有任何連接。

使用動態規劃的演算法

實現

Floyd演算法在不同的程式語言中均有大量的實現方法:

參考來源

  1. ^ 楊軍慶、安容瑾、任志國、張瀟贇、蔡曉龍. 基于佛洛依德算法的各院校间最短路径问题的求解. 《甘肅科技縱橫》. 2010年, (5): 28-29 [2020-08-09]. (原始內容存檔於2011-02-24). 
  2. ^ Stefan Hougardy. The Floyd–Warshall algorithm on graphs with negative cycles. Information Processing Letters. 2010年4月, 110 (8-9): 279–281 [2015-04-11]. doi:10.1016/j.ipl.2010.02.001. (原始內容存檔於2015-09-24) (英語). 
  3. ^ Skiena, Steven. The Algorithm Design Manual (PDF) 2. Springer. 2008-07-26: 212 [2015-04-11]. ISBN 978-0073523408. doi:10.1007/978-1-84800-070-4. (原始內容 (PDF)存檔於2015-06-09) (英語). 
  4. ^ Introduction to Algorithms [演算法導論]. 機械工業出版社. 2006: 386 [2001]. ISBN 9787111187776 (中文(中國大陸)). 
  5. ^ Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh. Algorithms (PDF) 1. McGraw-Hill Science/Engineering/Math. 2006-09-13: 176 [2015-04-11]. ISBN 978-0073523408. (原始內容 (PDF)存檔於2015-02-13) (英語). 

參見