前面Dijkstra算法和Bellman-Ford算法解決了單源最短路徑問題，但是如果需要獲取圖中任意兩頂點的最短 距離呢？我們可以使用前面兩個算法我們可以遍曆每個頂點得到每個頂點的單源最短距離，但是最短路徑算法中 提供了一種更為簡單的算法幫助我們實現任意兩頂點最短距離(Floyd)。

Floyd算法又稱為插點法，是一種利用動态規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法，與Dijkstra算法類似。 該算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授

使用鄰接矩陣G來表示圖，初始化G，将不可直達的頂點初始化為無窮大，定義k結點，遍曆N個頂點->k，使用k作為任意兩頂點i,j之間的中介點，

如果G[i][j]>G[i][k] G[k][j]，則執行松弛操作，這裡我們就可以理解為什麼叫插點法了，将每一個頂點當作中介點放入任意兩頂點之間，

如果可以執行松弛操作，則進行松弛。

V0->V1 1 V0->V2 2 V1->V2 -1

初始化圖G，執行如下操作

第一輪：

第一步：選取V0作為中介點

第二步：插入任意兩頂點之間

首先插入V0->V0之間，G[0][0]>G[0][0] G[0][0]，(0>0不滿足)無需松弛，

再插入V0->V1之間，G[0][1]>G[0][0] G[0][1],(1>0 1不滿足)無需松弛，

再插入V0->V2之間，G[0][2]>G[0][0] G[0][2],(2>0 2不滿足)無需松弛。

首先插入V1->V0之間，G[1][0]>G[1][0] G[0][0]，(∞>∞ 0不滿足)無需松弛，

再插入V1->V1之間，G[1][1]>G[1][0] G[0][1],(∞>∞ 1不滿足)無需松弛，

再插入V1->V2之間，G[1][2]>G[1][0] G[0][2],(∞>∞ 2不滿足)無需松弛。

......

第二輪在選取V1作為中介點，重複上面操作(這一輪會松弛 G[0][2]>G[0][1] G[1][2]->2>1 (-1) 滿足條件，松弛)

第二輪在選取V2作為中介點，重複上面操作

最終得到最短路徑

// // main.cpp // Floyd // // Created by 陳龍 // Copyright © 2019 陳龍. All rights reserved. // #include <iostream> using namespace std; int N,E; int main(int argc, const char * argv[]) { //N個頂點，E條邊 cin>>N>>E; int u,v,w; int G[N][N]; //初始化無窮大 for (int i=0; i<N; i ) {//頂點i for (int j=0; j<N; j ) {//目标頂點i if(i==j)G[i][j]=0; else G[i][j]=INT_MAX; } } //構建有向圖 for(int i=0;i<E;i ){ cin>>u>>v>>w; G[u][v] = w; } //動态規劃找中介 for (int k=0; k<N; k ) {//中介k for (int i=0; i<N; i ) {//頂點i for (int j=0; j<N; j ) {//目标頂點i if((G[i][k]!=INT_MAX && G[k][j] !=INT_MAX ) && G[i][j]>G[i][k] G[k][j]){ G[i][j]=G[i][k] G[k][j]; } } } } //最短路徑 cout<<"==="; for (int i=0; i<N; i ) {//頂點i for (int j=0; j<N; j ) {//目标頂點i cout<<i<<" "<<j<<" "<<G[i][j]<<endl; } } return 0; } /* eg: 3 3 0 1 1 0 2 2 1 2 -1 /*

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!