因爱智能

所有顶点对之间的最短路径

http://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

评论