Floyd算法(各对顶点之间的最短距离)

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算法(各对顶点之间的最短距离)
/*每对顶点之间最短路径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;
}
Floyd算法(各对顶点之间的最短距离)

上一篇:Floyd算法


下一篇:《图论》——最短路径 Dijkstra算法(戴克斯特拉算法)