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