核心:
double Dijk(int a,int b)
{
    for(int i=1;i<=N;i++) {M[i]=G[a][i];inq[i]=0;}
    M[a]=0,inq[a]=1;
    for(int I=1;I<N;I++)
    {
        double Minn=100000000;
        int Min;
        for(int i=1;i<=N;i++)
        {
            if(!inq[i] && M[i]<Minn)
            {
                Minn=M[i];
                Min=i;
            }
        }
        inq[Min]=1;
        for(int i=1;i<=N;i++)
            if(!inq[i] && G[Min][i]<100000000)
                if(M[Min]+G[Min][i]<M[i])
                    M[i]=M[Min]+G[Min][i];
    }
    return M[b];
}
这一题用了一个改版,其中M数组记录松弛过程中的一个边,我们可以想到因为以后的每次松弛都会沿用原来松弛的某个边,于是我们可以用一个变量记录松弛中的最大边,最后返回它就行了.
改版:
double Dijk(int a,int b)
{
    for(int i=1;i<=N;i++) {M[i]=G[a][i];inq[i]=0;}
    M[a]=0,inq[a]=1;
    double Maxn=0;
    for(int I=1;I<N;I++)
    {
        double Minn=100000000;
        int Min;
        for(int i=1;i<=N;i++)
        {
            if(!inq[i] && M[i]<Minn)
            {
                Minn=M[i];
                Min=i;
            }
        }
        if(Minn>Maxn) Maxn=Minn;
        if(Min==b)
            return Maxn;
        inq[Min]=1;
        for(int i=1;i<=N;i++)
            if(!inq[i] && G[Min][i]<100000000)
                if(G[Min][i]<M[i])
                    M[i]=G[Min][i];
    }
}

• Re:最短路算法(Dijkstra) (1421) ztx804 2021-02-07 19:19:17