ACM

Floyd从入门到背诵(

Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定加权图的中多源点之间最短路径的算法,与Dijkstra算法类似。

百度百科

在图论的学习中我们有时会遇到这样一类问题:在一个给定的图中求某一些点到另一些点的最短路径的长度。

我们称这样的问题为多源最短路径问题

Floyd算法是如此的优美而暴力,面对这样一个看似棘手的问题(甚至有人已经打算写一个循环Dijkstra了)它只要五行,哦不,四行代码就能解决问题!因此很多选手往往不会去深究该算法的原理,而是直接将该算法当成板子直接背了下来(

示例如下(d[i][j]表示i到j的最短距离):

for (int k=1;k<=n;k++)
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j];

然而美中不足的是它的时间复杂度是O(n^3),所以Dijkstra和SPFA还得老老实实地学。

为什么Floyd算法能够如此优美地解决问题?

因为它运用到了优秀的动态规划思想,它的状态转移方程式为:f[i][j]=min{f[i][k]+f[k][j]};

如何证明Floyd算法的合理性?

本文取巧地使用了强归纳法:

设i到x中间编号最大的是x1,x到j中间编号最大的是x2。由于x是i到j中间编号最大的,那么显然x1<x,x2<x。

根据结论,k==x1时d[i][x]已经取得最小值,k==x2时d[x][j]已经取得最小值。那么当k==x时d[i][x]和d[x][j]肯定都已经取得了最小值。

因此k==x的时候,执行d[i][j]=min(d[i][j],d[i][x]+d[x][j])必然会取得d[i][j]的最小值。

Q.E.D.

有兴趣的同学可以通过其他途径了解更多有关此算法的证明。

Floyd算法的注意事项?

作为中转点的K必须置于循环最外层。

下面给出一道例题:HDU2544

代码如下:

#include<bits/stdc++.h>
using namespace std;
int d[200][200],n,m,a,b,c;
int main(){
	while(~scanf("%d%d",&n,&m)){
		if (n==0&&m==0) return 0;
		memset(d,63,sizeof(d));
		for (int i=0;i<m;i++){
			scanf("%d%d%d",&a,&b,&c);
			d[a][b]=d[b][a]=c;
		}
		for (int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
		printf("%d\n",d[1][n]);
	}
	return 0;
}

2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注