Floyd-Warshall演算法

Floyd-Warshall 演算法（英語：Floyd-Warshall algorithm）， 中文亦稱枋洛他德演算法抑是佛洛依德演算法，是解決任意兩點間的上短路徑的一種演算法，會當正確處理有向圖負權（毋過袂當存在負權迴路）的上短路徑問題，同時嘛予人用佇計算有向圖的遞移閉包。

Floyd-Warshall 演算法的時間複雜度做 $ O ( | V | ^ { 三 } ) $，空間複雜度做 $ O ( | V | ^ { 二 } ) $，其中 $ V $ 是點集。

原理

Floyd-Warshall 演算法的原理是動態的規劃。

設 $ D _ { i , j , k } $ 為對 $ i $ 到 $ j $ 的干焦以 $ ( 一 . . k ) $ 集合中的節點為中央節點的上短路徑的長度。

一 . 若上短路徑經過點 k，著 $ D _ { i , j , k }=D _ { i , k , k 影一 } + D _ { k , j , k 影一 } $； 二 . 若上短路徑不經過點 k，著 $ D _ { i , j , k }=D _ { i , j , k 影一 } $。

所以，$ D _ { i , j , k }={ \ mbox { min } } ( D _ { i , j , k 影一 } , D _ { i , k , k 影一 } + D _ { k , j , k 影一 } ) $。

佇實際演算法內底，為著儉約空間，會使直接佇咧原來空間迵天，按呢空間會當降到二維。

演算法描述

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

` ` ` 一letdist be a | V | × | V | array of minimum distances initialized to ∞ ( infinity ) 二for eachvertex _ v _ 三 dist [_ v _] [_ v _] ← 零四for eachedge ( _ u _ , _ v _ ) 五 dist [_ u _] [_ v _] ← w ( _ u _ , _ v _ ) _ / / the weight of the edge ( _ u _ , _ v _ ) _ 六for_ k _from一to| V | 七for_ i _from一to| V | 八for_ j _from一to| V | 九ifdist [_ i _] [_ j _] > dist [_ i _] [_ k _] + dist [_ k _] [_ j _] 十 dist [_ i _] [_ j _] ← dist [_ i _] [_ k _] + dist [_ k _] [_ j _] 十一end if ` ` `

其中 ` dist [i] [j] ` 表示因為點 $ i $ 到矣 $ j $ 的代價，當其實 ∞ 表示兩點之間無任何連接。

使用動態規劃的演算法

• 上長公共子序列
• Viterbi 演算法

實現

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：e 一千空七十一和 Rfast 揹仔內

參見

• 圖論上短路
• Dijkstra 演算法
• Bellman-Ford 演算法