整理自《數(shù)據(jù)結(jié)構(gòu)高分筆記》

1、算法思想

迪杰斯特拉算法可以得到從圖中某一頂點到圖中其余每個頂點的最短路徑。如果只要求算圖中任意一對頂點間的最短路徑，則通常用弗洛伊德算法。

關(guān)于弗洛伊德算法的原理，我們直接通過一個例子來體會一下：

上圖中對應(yīng)的鄰接矩陣為：

初始時要設(shè)置兩個矩陣A和Path，A用來記錄當前已經(jīng)求得的任意兩個頂點的最短路徑長度，Path用來記錄當前兩頂點間最短路徑上要經(jīng)過的中間頂點。

初始時：A和Path如下所示：

第一步
以0作為中間點，參照上一步矩陣的結(jié)果，檢測所有結(jié)點對，假設(shè)當前所檢測的頂點對為（i，j），如果A[i][j]>A[i][0] + A[0][j],則將A[i][j]改為A[i][0] + A[0][j]的值，并將Path[i][j]改為0.經(jīng)過本次檢測和修改，所得矩陣如下：

第二步
以1為中間節(jié)點，參照上一步矩陣的結(jié)果，檢測所有結(jié)點對，其中有：A[0][2]>A[0][1] + A[1][2]=9，所以將A[0][2]改為9，Path[0][2]改為1:

第三步
以2為中間節(jié)點，參照上一步矩陣的結(jié)果，檢測所有結(jié)點對，進行修改。

第四步
以3為中間節(jié)點，參照上一步矩陣的結(jié)果，檢測所有結(jié)點對，進行修改。

經(jīng)過上面的步驟，得到的最終的矩陣為：

由矩陣A可以得到圖中任意兩點之間的最短路徑長度，以及最短路徑所經(jīng)過的結(jié)點。