Floyd算法（各对顶点之间的最短距离）
在上篇文章中谈论到了如何求算单源最短路径，因此要想求各对顶点之间的距离，只需循环求算n次即可。还有另外一种方法来求算各对顶点之间的最短距离，就是Floyd算法，由于其算法过程比Dijkstra更容易理解，并且代码更简洁，因此当求算各对顶点之间的最短距离常采用Floyd算法。
一.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算法实质上是一个动态规划算法。
代码实现:
/*每对顶点之间最短路径Floyd 2011.8.27*/
#include <iostream>
#include <stack>
#define M 100
#define N 100
usingnamespace std;
typedef struct node
{
int matrix[N][M]; //邻接矩阵
int n; //顶点数
int e; //边数
}MGraph;
void FloydPath(MGraph g,int dist[N][M],int path[N][M])
{
int i,j,k;
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
{
if(g.matrix[i][j]>0)
{
dist[i][j]=g.matrix[i][j];
path[i][j]=i;
}
else
{
if(i!=j)
{
dist[i][j]=INT_MAX;
path[i][j]=-1;
}
else
{
dist[i][j]=0;
path[i][j]=i;
}
}
}
for(k=0;k<g.n;k++) //中间插入点(注意理解k为什么只能在最外层)
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
{
if((dist[i][k]>0&&dist[i][k]<INT_MAX)&&//防止加法溢出
(dist[k][j]>0&&dist[k][j]<INT_MAX)&&
dist[i][k]+dist[k][j]<dist[i][j])
{
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=path[k][j]; //path[i][j]记录从i到j的最短路径上j的前一个顶点
}
}
}
void showPath(int path[N][M],int s,int t) //打印出最短路径
{
stack<int> st;
int v=t;
while(t!=s)
{
st.push(t);
t=path[s][t];
}
st.push(t);
while(!st.empty())
{
cout<<st.top()<<"";
st.pop();
}
}
int main(int argc, char*argv[])
{
int e,n;
while(cin>>e>>n&&e!=0)
{
int i,j;
int s,t,w;
MGraph g;
int dist[N][M],path[N][M];
g.n=n;
g.e=e;
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
g.matrix[i][j]=0;
for(i=0;i<e;i++)
{
cin>>s>>t>>w;
g.matrix[s][t]=w;
}
FloydPath(g,dist,path);
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
{
if(dist[i][j]>0&&dist[i][j]<INT_MAX)
{
showPath(path,i,j);
cout<<dist[i][j]<<endl;
}
}
}
return0;
}
