Floyd-Warshall算法

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

Floyd-Warshall算法
概況
類別	全局最短路徑問題（適用於帶權圖）
資料結構	圖
複雜度
平均時間複雜度	${\displaystyle \Theta (|V|^{3})}$
最壞時間複雜度	${\displaystyle O(|V|^{3})}$
最優時間複雜度	${\displaystyle \Omega (|V|^{3})}$
空間複雜度	${\displaystyle \Theta (|V|^{2})}$
相關變量的定義
${\displaystyle V}$	點集

Floyd-Warshall算法的時間複雜度為${\displaystyle O(|V|^{3})}$^[4]，空間複雜度為${\displaystyle O(|V|^{2})}$，其中${\displaystyle V}$是點集。

原理

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

設${\displaystyle D_{i,j,k}}$為從${\displaystyle i}$到${\displaystyle j}$的只以${\displaystyle (1..k)}$集合中的節點為中間節點的最短路徑的長度。

1. 若最短路徑經過點k，則${\displaystyle D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}}$；
2. 若最短路徑不經過點k，則${\displaystyle D_{i,j,k}=D_{i,j,k-1}}$。

因此，${\displaystyle D_{i,j,k}={\mbox{min}}(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})}$。

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

算法描述

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]表示由點${\displaystyle i}$到點${\displaystyle j}$的代價，當其為 ∞ 表示兩點之間沒有任何連接。

使用動態規劃的算法

• 最長公共子序列
• 維特比算法

實現

Floyd算法在不同的編程語言中均有大量的實現方法：

• C++：boost::graph（頁面存檔備份，存於網際網路檔案館）庫下
• C#：QuickGraph（頁面存檔備份，存於網際網路檔案館）和QuickGraphPCL（頁面存檔備份，存於網際網路檔案館）中均有相關實現方法
• Java：Apache Commons Graph（頁面存檔備份，存於網際網路檔案館）庫中
• JavaScript：Cytoscape（英語：Cytoscape）庫中
• MATLAB：Matlab_bgl（頁面存檔備份，存於網際網路檔案館）包中
• Perl：Graph（頁面存檔備份，存於網際網路檔案館）組件下
• Python：SciPy庫下（scipy.sparse.csgraph（頁面存檔備份，存於網際網路檔案館）），NetworkX（英語：NetworkX）庫中也有
• R：e1071（頁面存檔備份，存於網際網路檔案館）和Rfast（頁面存檔備份，存於網際網路檔案館）包內

參考來源

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） （英語）.

參見

• 圖論最短路
• Dijkstra算法
• Bellman-Ford算法