所有顶点对之间的最短路径
https://blog.csdn.net/z690933166/article/details/8578198
求所有顶点对之间的最短路径的显而易见的方法是，每次以一个顶点为源点重复执行dijkstra算法n次来求得，总的执行时间为O(n^3).
下面介绍的是费罗伊德提出的另一个算法。该算法也是用邻接矩阵a表示有向网，其时间复杂度也是O(n^3)，但在形式上更简单些。
Floyd算法的基本思想是，从邻接矩阵a开始进行n次迭代，第一次迭代后a[i,j]的值是从Vi到Vj且中间不经过编号大于1的顶点(即V2~Vn)的最短路径长度。第k次迭代后a[i,j]的值是从Vi到Vj且中间不经过编号大于k的顶点(即Vk+1~Vn)的最短路径长度；经过第n次迭代后a[i,j]的值就是Vi到Vj的最短路径长度。其迭代公式为：
a(k)[i,j]=min{a(k-1)[i,j],a(k-1)[i,k]+a(k-1)[i,j]}
其中,1<=k<=n,迭代初值a0即为有向图的邻接矩阵。迭代公式的意义，如果第K次迭代时加点顶点Vk后，存在从Vi到Vk和从Vk到Vj的两条路径，且长度之和小于迭代前从Vi到Vj的路径长度，则更新为新路径的值，否则保留原有的值。
为了实现Floyd算法，还需引入一个矩阵path。path[i,j]是从Vi到Vj的最短路径上Vj前一个顶点的序号，并约定从Vi到Vj无路径时path[i,j]=0.在求得最短路径后由path[i,j]的值向前追溯，可以得到从Vi到Vj的最短路径。
void floyd(int a[][],int p[][],int n)//求有向网中所有顶点对之间的最短路径
{
int i,j,k;//定义局部变量
for(i=1;i<=n;i++)//对path数组初始化，假定邻接矩阵已存入a数组中
for(j=1;j<=n;j++)
if(i==j)
path[i][j]=0;
else if(a[i][j]<max)
path[i][j]=i;
else
path[i][j]=0;
for(k=1;k<=n;k++)//迭代求最短路径及其长度
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][k]+a[k][j]>a[i][j])
{
a[i][j]=a[i][k]+a[k][j];
path[i][j]=path[k][j];
}
}//floyd
评论