All Sources Shortest Path The Floyd-Warshall Algorithm 陳章裕 主講 高一資訊專題 2012.06.26

The Floyd-Warshall Algorithm Floyd-Warshall演算法，簡稱Floyd演算法，用於求解任意兩點間的最短距離，時間複雜度為O(n^3)。我們平時所見的Floyd演算法的一般形式如下： 1 void Floyd(){ 2     int i,j,k; 3     for(k=1;k<=n;k++) 4         for(i=1;i<=n;i++) 5             for(j=1;j<=n;j++) 6                 if(d[i][k]+d[k][j]<d[i][j]) 7                     d[i][j]=d[i][k]+d[k][j]; 8 }

The Floyd-Warshall Algorithm 【說明範例】某王國有四個城市A, B, C, D，這些城市並非直接相通。例如下圖A城市可直接到C城市，但卻無法直接到B或D城市。城市之間可通行的情況及距離，如下圖所示。請問由C城市到A城市的最短距離？ A B C D 3 2 7 1 6 A B C D 7 1 2 6 3 輸入： 4 0 0 3 0 2 0 0 0 0 7 0 1 6 0 0 0 輸出： 0 10 3 4 2 0 5 6 7 7 0 1 6 16 9 0

The Floyd-Warshall Algorithm void floyd_warshall() { int i, j, k; for (k = 0; k < n; ++k) for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) // 如果i-k及k-j之間的路徑存在，且i,j 為不同節點 if ((d[i][k] * d[k][j] != 0) && (i != j)) if ((d[i][k]+d[k][j]<d[i][j]) ||(d[i][j]==0)) d[i][j] = d[i][k] + d[k][j]; }

The Floyd-Warshall Algorithm k i j d[i][j] d[i][k] + d[k][j] result 0 + 0 1 2 3 0 + 3 2 + 0 2 + 3 5 7 6 6 + 0 6 + 3 9 if ((d[i][k] * d[k][j] != 0) && (i != j))　　　//灰 if ((d[i][k]+d[k][j]<d[i][j]) ||(d[i][j]==0))//黑 d[i][j] = d[i][k] + d[k][j]; 　　　　//紅 1 2 3 5 7 6 9 A B C D 7 1 2 6 3

The Floyd-Warshall Algorithm k i j d[i][j] d[i][k] + d[k][j] result 1 0 + 2 0 + 0 2 3 0 + 5 5 7 + 2 9 7 7 + 0 7 + 5 6 if ((d[i][k] * d[k][j] != 0) && (i != j))　　　//灰 if ((d[i][k]+d[k][j]<d[i][j]) ||(d[i][j]==0))//黑 d[i][j] = d[i][k] + d[k][j]; 　　　　//紅 1 2 3 5 9 7 6 A B C D 7 1 2 6 3

The Floyd-Warshall Algorithm k i j d[i][j] d[i][k] + d[k][j] result 2 3 + 9 1 3 + 7 10 3 3 + 0 3 + 1 4 5 + 9 5 + 7 5 5 + 0 5 + 1 6 9 0 + 9 7 0 + 7 0 + 0 0 + 1 9 + 9 9 + 7 16 9 + 0 9 + 1 if ((d[i][k] * d[k][j] != 0) && (i != j))　　　//灰 if ((d[i][k]+d[k][j]<d[i][j]) ||(d[i][j]==0))//黑 d[i][j] = d[i][k] + d[k][j]; 　　　　//紅 1 2 3 10 4 5 6 9 7 16 A B C D 7 1 2 6 3

The Floyd-Warshall Algorithm k i j d[i][j] d[i][k] + d[k][j] result 3 4 + 6 1 10 4 + 16 2 4 + 9 4 4 + 0 6 + 6 6 + 16 5 6 + 9 6 6 + 0 9 1 + 6 7 1 + 16 1 + 9 1 + 0 0 + 6 16 0 + 16 0 + 9 0 + 0 if ((d[i][k] * d[k][j] != 0) && (i != j))　　　//灰 if ((d[i][k]+d[k][j]<d[i][j]) ||(d[i][j]==0))//黑 d[i][j] = d[i][k] + d[k][j]; 　　　　//紅 1 2 3 10 4 5 6 7 16 9 A B C D 7 1 2 6 3

The Floyd-Warshall Algorithm // floyd-warshall.cpp Floyd_Warshall Algorithm #include <iostream> using namespace std; int n; // 節點數 int d[16][16]; void floyd_warshall() { int i, j, k; for (k = 0; k < n; ++k) for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) // 如果i-k及k-j之間的路徑存在，且i,j 為不同節點 if ((d[i][k] * d[k][j] != 0) && (i != j)) if ((d[i][k]+d[k][j]<d[i][j]) ||(d[i][j]==0)) d[i][j] = d[i][k] + d[k][j]; } int main() { int i, j; cin>>n; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) cin>>d[i][j]; floyd_warshall(); for (j = 0; j < n; ++j) cout.width(3); cout<<d[i][j]; } cout<<endl; system("pause"); return 0;

The Floyd-Warshall Algorithm 【zerojudge 範例】 // Zerojudge d908. 4. 最佳路徑 #include <iostream> #include<cstring> using namespace std; int n; int d[101][101]; void floyd_warshall() { int i, j, k; for (k = 0; k < n; ++k) for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) if ((d[i][k] * d[k][j] != 0) && (i != j)) if ((d[i][k]+d[k][j]>d[i][j]) ) d[i][j] = d[i][k] + d[k][j]; } int main() { char c; int i, j; while(cin>>c>>n) int w,m=0; char a ,b; memset(d,0,sizeof(d)); for (i = 0; i < n; ++i) cin>>a>>b>>w; if(w > d[a-'A'][b-'A']) d[a-'A'][b-'A']=w; } floyd_warshall(); for (j = 0; j < n; ++j) m=(m>d[c-'A'][j])?m:d[c-'A'][j]; cout<<m<<endl; //system("pause"); return 0;

【zerojudge 練習】 b017 E. 漢米頓的麻煩 b029 D. 水之都 d282 Q11015: 05-2 Rendezvous d335　 10009 - All Roads Lead Where? d792 　11463 - Commandos d908 　4. 最佳路徑