檢視 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 演算法的虛擬碼是描述如下：

` ` `
一'''let'''dist be a | V | × | V | array of minimum distances initialized to ∞ ( infinity )
二'''for each'''vertex _ v _
三 dist [_ v _] [_ v _] ← 零四'''for each'''edge ( _ 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 |
九'''if'''dist [_ 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 演算法

[[分類: 待校正]]