Floyd-Warshall演算法(英語:Floyd-Warshall algorithm),中文亦稱弗洛伊德演算法或佛洛依德演算法[1],是解決任意兩點間的最短路徑的一種演算法[2],可以正確處理有向圖或負權(但不可存在負權迴路)的最短路徑問題,同時也被用於計算有向圖的遞移閉包[3]。
原理
設為從到的只以集合中的節點為中間節點的最短路徑的長度。
- 若最短路徑經過點k,則;
- 若最短路徑不經過點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演算法在不同的程式語言中均有大量的實現方法:
- C++:boost::graph(頁面存檔備份,存於互聯網檔案館)庫下
- C#:QuickGraph(頁面存檔備份,存於互聯網檔案館)和QuickGraphPCL(頁面存檔備份,存於互聯網檔案館)中均有相關實現方法
- Java:Apache Commons Graph(頁面存檔備份,存於互聯網檔案館)庫中
- JavaScript:Cytoscape庫中
- MATLAB:Matlab_bgl(頁面存檔備份,存於互聯網檔案館)包中
- Perl:Graph(頁面存檔備份,存於互聯網檔案館)組件下
- Python:SciPy庫下(scipy.sparse.csgraph(頁面存檔備份,存於互聯網檔案館)),NetworkX庫中也有
- R:e1071(頁面存檔備份,存於互聯網檔案館)和Rfast(頁面存檔備份,存於互聯網檔案館)包內
參考來源
參見
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.