一.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