Floyd算法及其应用

Part I-Introduction

Floyd算法是一种求图上多源最短路径的算法,适用于中小规模的图,思维简单易懂。

Floyd算法的实质是(区间)动态规划,在这里做一个简单的概述。

对于一个有\(n\)个结点的图,

令\(dis[i][j]\)为结点\(i\)到结点\(j\)的最短路径长度。

首先,将所有现成的边都存入\(dis\),其余的令其值\(=\infty\),并使\(dis[i][i]=0\)。

接着,枚举中转点(\(k\)),那么:

\[dis[i][j]=\min\{dis[i][k]+dis[k][j]\text{ | }k\in[1,n],k\ne i,k\ne j\}\]

代码实现:

void Floyd()
{
    memset(dis,0x3f3f3f3f,sizeof(dis));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]!=-1)//如果边(i,j)存在。
                dis[i][j]=a[i][j];//a为现存的边。
    for(int i=1;i<=n;i++) dis[i][i]=0;
    for(int k=1;k<=n;k++)//枚举中转点。
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(i==j||j==k||k==i) continue;
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
}

Attention:循环时\(k\)必须放在第一维。

上一篇:结构体的强制装换


下一篇:BAPC2018 K kingpin escape