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\)必须放在第一维。