漫畫：如何求圖的最短路徑？ | 技術頭條

作者 | 程序員小灰

本文經授權轉載自程序員小灰（ID：chengxuyuanxiaohui）

————— 第二天 —————

小灰的思路如下：

第一步，利用迪傑斯特拉演算法的距離表，求出從頂點A出發，到其他各個頂點的最短距離：

第二步，繼續使用迪傑斯特拉演算法，求出從頂點B出發，到其他各個頂點的最短距離。

第三步，從頂點C出發，到各個頂點的最短距離。

第四步，從頂點D出發......

.......

就像這樣，一直遍歷到頂點G。

這個思路的時間複雜度是多少呢？

假如圖中有n個頂點，如果不考慮堆優化，一次迪傑斯特拉演算法的時間複雜度是O（n^2）。所以，把每一個頂點都計算一遍，總的時間複雜度是O（n^3）。

舉一個栗子：

上圖的頂點A和頂點C沒有直接相連的邊，它們之間的直接距離是無窮大。

如果以B作為「中繼頂點」，此時A到C的最短路徑就是A-B-C，最短距離是3+2=5。

再舉一個栗子：

上圖的頂點A和頂點C直接相連，距離是6。但是存在一條「迂迴」路徑A-B-C，距離是3+2=5<6。

所以，經過中繼頂點B，從A到C的最短距離可以是5。

下面我們來看一看Floyd演算法的詳細步驟。

1.要實現Floyd演算法，首先需要構建帶權圖的鄰接矩陣：

在鄰接矩陣當中，每一個數字代表著從某個頂點到另一個頂點的直接距離，這個距離是沒有涉及到任何中繼頂點的。

2.此時假定只允許以頂點A作為中繼頂點，那麼各頂點之間的距離會變成什麼樣子呢？

B和C之間的距離原本是無窮大，此時以A為中繼，距離縮短為AB距離+AC距離=

5+2=7。

更新對應矩陣元素（橙色區域代表頂點A到其他頂點的臨時距離）：

3.接下來以頂點A、B作為中繼頂點，那麼各頂點之間的距離會變成什麼樣子呢？

A和D之間的距離原本是無窮大，此時以B為中繼，距離縮短為AB距離+BD距離=5+1=6。

A和E之間的距離原本是無窮大，此時以B為中繼，距離縮短為AB距離+BE距離=5+6=11。

更新對應矩陣元素（橙色區域代表頂點B到其他頂點的臨時距離）：

4.接下來以頂點A、B、C作為中繼頂點，那麼各頂點之間的距離會變成什麼樣子呢？

A和F之間的距離原本是無窮大，此時以C為中繼，距離縮短為AC距離+CF距離=2+8=10。

更新對應矩陣元素（橙色區域代表頂點C到其他頂點的臨時距離）：

以此類推，我們不斷引入新的中繼頂點，不斷刷新矩陣中的臨時距離。

最終，當所有頂點都可以作為中繼頂點時，我們的距離矩陣更新如下：

此時，矩陣中每一個元素，都對應著某頂點到另一個頂點的最短距離。

為什麼這麼說呢？讓我們回顧一下動態規劃的兩大要素：

問題的初始狀態

問題的狀態轉移方程式

對於尋找圖的所有頂點之間距離的問題，初始狀態就是頂點之間的直接距離，也就是鄰接矩陣。

而問題的狀態轉移方程式又是什麼呢？

假設新引入的中繼頂點是n，那麼：

頂點i 到 頂點j 的新距離 = Min（頂點i 到 頂點j 的舊距離，頂點i 到 頂點n 的距離+頂點n 到 頂點j 的距離）

final static int INF = Integer.MAX_VALUE;
public static void floyd(int[][] matrix){
//循環更新矩陣的值
for(int k=0; k<matrix.length; k++){
for(int i=0; i<matrix.length; i++){
for(int j=0; j<matrix.length; j++){
if(matrix[i][k] == INF || matrix[k][j] == INF) {
continue;
}
matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
}
}
}
// 列印floyd最短路徑的結果
System.out.printf("最短路徑矩陣:
");
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++)
System.out.printf("%3d ", matrix[i][j]);
System.out.printf("
");
}
}
public static void main(String[] args) {
int[][] matrix = {
{0, 5, 2, INF, INF, INF, INF},
{5, 0, INF, 1, 6, INF, INF},
{2, INF, 0, 6, INF, 8, INF},
{INF, 1, 6, 0, 1, 2, INF},
{INF, 6, INF, 1, 0, INF, 7},
{INF, INF, 8, 2, INF, 0, 3},
{INF, INF, INF, INF, 7, 3, 0}
};
floyd(matrix);
}

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！