Dijkstra算法是求源點到其他各個頂點的最短路徑，如果求解任意兩個頂點的最短路徑，則需要以每個頂點為源點，重復(fù)調(diào)用n次Dijkstra算法。完全沒有必要這么麻煩，下面介紹的Floyd算法可以求解任意兩個頂點的最短路徑。Floyd算法又稱為插點法，其算法核心是在頂點i到頂點j之間，插入頂點k，看是否能夠縮短i和j之間的距離（松弛操作）。

算法步驟：

1）數(shù)據(jù)結(jié)構(gòu)。

設(shè)置地圖的帶權(quán)鄰接矩陣為G.Edge[ ][ ]，即如果從頂點i 到頂點j有邊，就讓G.Edge[i][j] = <i,j>的權(quán)值，否則G.Edge[i][j] = 無窮大；采用兩個輔助數(shù)組；最短距離數(shù)組dist[ i][j]，記錄從i 到j(luò)頂點的最短路徑長度；前驅(qū)數(shù)組p[i][j],記錄從 i 到j(luò)頂點的最短路徑上j頂點的前驅(qū)。

2）初始化。

初始化dist[i][j] = G.Edge[i][j],如果頂?shù)譱 到頂點j 有邊相連，初始化p[i][j] = i,否則p[i][j] = -1。

3）插點。

其實就是在i,j之間插入頂點k,看是否能夠縮短i和j之間距離（松弛操作）。如果dist[i][j] >dist[i][k] +dist[k][j],則dist[i][j] = dist[i][k] + dist[k][j],記錄頂點j 的前驅(qū)為：p[i][j] = p[k][j]。

一個例子：

1）數(shù)據(jù)結(jié)構(gòu)：

設(shè)置地圖的帶權(quán)鄰接矩陣為G.Edge[ ][ ],即如果從頂點i 到頂點j有邊，就讓G.Edge[i][j] = <i,j>的權(quán)值，當(dāng) i = j 時， G.Edge[i][j] = 0,否則G.Edge[i][j] = 無窮大。

2）初始化

初始化最短距離數(shù)組dist[i][j] = G.Edge[i][j] ;如果頂點i 到 j有邊相連，初始化前驅(qū)數(shù)組p[i][j] =i，否則p[i][j] = -1。初始化后的dist[ ]和p[ ][ ]，如圖所示：

3）插點（插頂點0，k=0）

其實就是借點，借東風(fēng)，大家一起借頂點0更新最短距離。如果dist[i][j] > dist[i][0]+dist[0][j],則dist[i][j] = dist[i][0] + dist[0][j]，記錄頂點j的前驅(qū)為：

p[i][j] = p[0][j]。

誰可以借頂點0呢？

看頂點0的入邊，2--->0，也就是說頂點2可以借0點，更新2到其他頂點的最短距離。（程序中通過窮舉所有頂點來判斷是否可以借0點）。

dist[2][1]:? ? dist[2][1] = 5 > dist[2][0] + dist[0][1] = 4,則更新dist[2][1] = 4,p[2][1] = 0;如圖所示：

4）插點（插頂點1，k = 1）

大家一起借頂點1更新最短距離。誰可以借頂點1呢？

看頂點1的入點，頂點0、2都可以借1點，更新其到其他頂點的最短距離。

dist[0][2]:? ? dist[0][2] = 無窮大 > dist[0][1] +dist[1][2] = =10,則更新dist[0][2] = 10,p[0][2] = 1;

5)插點（插頂點2，k=2）

大家一起借頂點2，更新最短距離。從頂點2的入邊可知，1，3可以借。

6）插點（插頂點3，k=3）

大家一起借頂點3，更新最短距離?？错旤c3的入邊，頂點0、1、2都可以借3點。

7）插點結(jié)束。

dist[][]數(shù)組即為各頂點之間的最短距離，如果想找頂點i 到頂點j的最短路徑，可以根據(jù)前驅(qū)數(shù)組p[][]獲得。

例如：

1）求1到2的最短路徑，首先讀取p[1][2] = 3,說明頂點2的前驅(qū)為3，繼續(xù)向前找，讀取p[1][3] = 1,說明3的前驅(qū)為1，得到1到2的最短路徑為1-> 3->2。

2）求1到0的最短路徑，首先讀取p[1][0] = 2,說明頂點0的前驅(qū)為2，繼續(xù)向前找，讀取p[1][2] = 3,說明2的前驅(qū)為3，繼續(xù)向前找，讀取p[1][3] =1，得到1到0的最短路徑為1->3->2->0。