Floyd计算最短路径问题

Floyd计算有向图所有点对的最短路径问题
问题】:设G=(V,E)是一个有向图,其中的每条边(i,j)有一个非负长度L[i][j],如果从顶点i到顶点j没有边,则L[i][j]=0,这里我们要解决问题就是:找出从每个顶点到其他所有顶点的距离D[i][j]
解题】:这里我们要用动态划分算法来解决这个问题:用自底向上的递推式方法来处理。先将L[i][j]中的值全部复制到D[i][j]中,然后通过3重for循环对D[N][N]进行N-1次迭代。保证D[i][j]为最小值。该算法的时间复杂度:o(n3),空间复杂度:o(n2);这就是floyd求最短路径的算法
程序】:代码如下
#include<iostream.h>
#define N 6
int l[N][N],D[N][N];
void floyd()
{
    int i,j,k;
    for(i=1;i<N;i++)
        for(j=1;j<N;j++)
            D[i][j]=l[i][j];
    for(k=1;k<N;k++)
        for(i=1;i<N;i++)
            for(j=1;j<N;j++)
            {
                int m;
                if(i!=j && D[i][k]!=0 && D[k][j]!=0)
                {
                    m=D[i][k]+D[k][j];
                    if(D[i][j]==0)
                        D[i][j]=m;
                    else if(m<D[i][j])
                        D[i][j]=m;
                }
            }
}

void main()
{
    for(int i=1;i<N;i++)
    {    for(int j=1;j<N;j++)
            cin>>l[i][j];
    }
    cout<<endl;
    floyd();
    for(i=1;i<N;i++)
    {    for(int j=1;j<N;j++)
            cout<<D[i][j]<<" ";
        cout<<endl;
    }
}

留言

Your email address will not be published. Required fields are marked *