java實作Floyd算法

1 問題描述

何為Floyd算法？

Floyd算法功能：給定一個權重連通圖，求取從每一個頂點到其它所有頂點之間的最短距離。（PS：其實作功能也稱完全最短路徑問題）

Floyd算法思想：将頂點i到j的直接距離依次與頂點i到頂點j之間加入k個中間節點之後的距離進行比較，從中選出最短的一組距離，即為頂點i到頂點j的最短距離，然後重複上述步驟求取其它頂點之間的最短距離。

2 解決方案

2.1 使用Floyd算法得到最短距離示例

此處借用《算法設計與分析基礎》第3版上一個插圖：

其中，

D(0)表示不包含中間節點，即給定圖的原始權重矩陣；

D(1)表示加入一個中間節點a；

D(2)表示在D(1)的基礎上再加入一個中間節點b；

D(3)表示在D(2)的基礎上再加入一個中間節點c；

D(4)表示在D(3)的基礎上再加入一個中間節點d，這時就可得到最終結果。

每次加入一個中間節點後，都要更新所有頂點之間的最短距離，直到所有頂點均可以作為中間頂點之後，才算更新完畢，即可得到最終結果。

2.2 具體編碼

Floyd是計算每對頂點間最短路徑的經典算法，其采用的思想是動态規劃法。

時間複雜度是雷打不動的O(n^3)。

注意，Floyd算法計算最短距離可以有負權值的邊，但不能有權值和為負數的回路。

下面代碼中所用圖的資料便是2.1中示例圖的資料。

運作結果：