一.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 
     
        4 #include 
      
         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
       
        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
        
         0&&dist[i][k]
         
          0&&dist[k][j]
          

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<

<<" "; 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

>s>>t>>w; 90 g.matrix[s][t]=w; 91 } 92 FloydPath(g,dist,path); 93 for(i=0;i

0&&dist[i][j]