Floyd算法实现

原理

我们从一个点i到另一个点j,无非就两种走法

• 直接从i到j
• 通过中间点k中转，$i⟶k⟶j$
  （在经过多个中间点的时候也是一样的，$i⟶k_1⟶k_2⟶...⟶j$，经过的这么多中转都可以划分成多段通过一个中间点中转的做法）

实现

e 二维数组保存的是顶点之间边的关系
 
e[i][j] 为顶点 i 与顶点 j 之间边的权值
 
假设顶点有n个

 
1.通过顶点1中转（即k=1），更新得到顶点i到其他顶点j的 通过中转顶点1 得到的当前最短路径。
e[i][1]、e[1][j] 表示顶点i通过顶点1到顶点j

for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)
		if (e[i][1] != INT_MAX && e[1][j] != INT_MAX && e[i][j] > e[i][1] + e[1][j])
			e[i][j] = e[i][1] + e[1][j];

e[i][1] + e[1][j]为i通过1到j所需的代价（权），与 e[i][j] 比较的意思为：i到j是通过直接到达的代价小还是通过中转1到达的代价小，将两者的代价的最小值保存入 e[i][j]。

2.在通过顶点1中转的基础上，再求每个顶点通过顶点2中转到其他顶点的当前最短路径

for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)
		if (e[i][1] != INT_MAX && e[1][j] != INT_MAX && e[i][j] > e[i][1] + e[1][j])
			e[i][j] = e[i][1] + e[1][j];

for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)
		if (e[i][2] != INT_MAX && e[2][j] != INT_MAX && e[i][j] > e[i][2] + e[2][j])
			e[i][j] = e[i][2] + e[2][j];

3.一直尝试到通过1、2、3、…、n这n个顶点做中转，即可更新出每个顶点到其他顶点的最短路径
可以直接外套一个循环达到这个效果

for (k = 1; k <= n; k++)
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (e[i][k] != INT_MAX && e[k][j] != INT_MAX && e[i][j] > e[i][k] + e[k][j])
				e[i][j] = e[i][k] + e[k][j];