Floyd算法

编程与算法

Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。

此算法由Robert W. Floyd（罗伯特·弗洛伊德）于1962年发表在“Communications of the ACM”上。同年Stephen Warshall（史蒂芬·沃舍尔）也独立发表了这个算法。Robert W．Floyd这个牛人是朵奇葩，他原本在芝加哥大学读的文学，但是因为当时美国经济不太景气，找工作比较困难，无奈之下到西屋电气公司当了一名计算机操作员，在IBM650机房值夜班，并由此开始了他的计算机生涯。

核心思路

Floyd是通过权值矩阵得到各个节点之间最短路径的方法。他的核心思路就是一个松弛方程：

1
map[i,j]:= min{ map[i,k] + map[k,j], map[i,j] }

map[i,j]表示i与j之间的路径权值。

枚举所有的节点k 1->n，将该节点(k)当成任意两点(i 1->n , j 1->n)的中间节点，判断是否会降低路径的权值(map[i,j],map[i,k]+map[k,j])。

通过这种方法枚举一遍，遍可以得到权值最小的权值矩阵了。

算法举例

有向图：
graph

然后建立一个权值矩阵：

1
	A	B	C	D
A	0	2	6	4	
B	x	0	3	x
C	7	x	0	1
D	5	x	12	0

首先枚举A为中间点，开始进行第一轮松弛，
之后得到新的矩阵：

1
0	2	6	4
x	0	3	x
7	9	0	1
5	7	11	0

此时更新了C->B,D->B,D->C的权值。

然后以B为中间点，继续进行松弛：

1
0	2	5	4
x	0	3	x
7	9	0	1
5	7	10	0

以C为中间点，继续松弛:

1
0	2	5	4
10	0	3	4
7 	9	0	1
5	7	10	0

最后以D为中间的：

1
0	2	5	4
9	0	3	4
6	8	0	1
5	7	10	0

最后得到的新的权值矩阵就是各个节点之间的最短路径。

算法实现

这里就写C&&C++的吧，只有三个循环，其实很简单的：

1
2
3
4
5
6
void floyd(int n){
	for(int t=1; t<=n; t++)  
		for(int i=1; i<=n; i++)  
			for(int j=1; j<=n; j++)  
				dis[i][j]=min(dis[i][j],dis[i][t]+dis[t][j]);  
}