一.Floyd算法

??假設從i到j的最短路徑上要經過若干個頂點，這些中間頂點中最大的頂點編號為k，最小的頂點為t，因此要求算dist[i][j]的最小值，那么只需要求算dist[i][s]+dist[s][j](t<=s<=k)的所有值，并取其中最小者即可。因此可以設置一個中間頂點k(0<=k<n)分別插入到每隊頂點(i,j)之中，并更新dist[i][j]的值。當n個頂點插入到每隊頂點之中，求解便結束了。其實Floyd算法實質上是一個動態規劃算法。

1 /*每對頂點之間最短路徑Floyd 2011.8.27*/ 2 3 #include <iostream> 4 #include <stack> 5 #define M 100 6 #define N 100 7 using namespace std; 8 9 typedef struct node 10 { 11 int matrix[N][M]; //鄰接矩陣 12 int n; //頂點數 13 int e; //邊數 14 }MGraph; 15 16 void FloydPath(MGraph g,int dist[N][M],int path[N][M]) 17 { 18 int i,j,k; 19 for(i=0;i<g.n;i++) 20 for(j=0;j<g.n;j++) 21 { 22 if(g.matrix[i][j]>0) 23 { 24 dist[i][j]=g.matrix[i][j]; 25 path[i][j]=i; 26 } 27 else 28 { 29 if(i!=j) 30 { 31 dist[i][j]=INT_MAX; 32 path[i][j]=-1; 33 } 34 else 35 { 36 dist[i][j]=0; 37 path[i][j]=i; 38 } 39 } 40 } 41 for(k=0;k<g.n;k++) //中間插入點(注意理解k為什么只能在最外層) 42 for(i=0;i<g.n;i++) 43 for(j=0;j<g.n;j++) 44 { 45 if((dist[i][k]>0&&dist[i][k]<INT_MAX)&& //防止加法溢出 46 (dist[k][j]>0&&dist[k][j]<INT_MAX)&& 47 dist[i][k]+dist[k][j]<dist[i][j]) 48 { 49 dist[i][j]=dist[i][k]+dist[k][j]; 50 path[i][j]=path[k][j]; //path[i][j]記錄從i到j的最短路徑上j的前一個頂點 51 } 52 } 53 } 54 55 void showPath(int path[N][M],int s,int t) //打印出最短路徑 56 { 57 stack<int> st; 58 int v=t; 59 while(t!=s) 60 { 61 st.push(t); 62 t=path[s][t]; 63 } 64 st.push(t); 65 while(!st.empty()) 66 { 67 cout<<st.top()<<" "; 68 st.pop(); 69 } 70 71 } 72 73 int main(int argc, char *argv[]) 74 { 75 int e,n; 76 while(cin>>e>>n&&e!=0) 77 { 78 int i,j; 79 int s,t,w; 80 MGraph g; 81 int dist[N][M],path[N][M]; 82 g.n=n; 83 g.e=e; 84 for(i=0;i<g.n;i++) 85 for(j=0;j<g.n;j++) 86 g.matrix[i][j]=0; 87 for(i=0;i<e;i++) 88 { 89 cin>>s>>t>>w; 90 g.matrix[s][t]=w; 91 } 92 FloydPath(g,dist,path); 93 for(i=0;i<g.n;i++) 94 for(j=0;j<g.n;j++) 95 { 96 if(dist[i][j]>0&&dist[i][j]<INT_MAX) 97 { 98 showPath(path,i,j); 99 cout<<dist[i][j]<<endl; 100 } 101 } 102 } 103 return 0; 104 }

(轉)http://www.cnblogs.com/dolphin0520/archive/2011/08/27/2155542.html

?

總結

以上是生活随笔為你收集整理的最短路径算法----floyd（转）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。