Floyd算法

发表于2022-02-28字数统计1.2k阅读时长9分

Floyd（弗洛伊德）算法用于计算图的两结点之间的最短路径问题，时间复杂度为$O(n^3)$，空间复杂度为$O(n^2)$

Floyd算法

复杂度比较高，但是常数小，容易实现。（我会说只有三个 for 吗？）

适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）

基本思想

使用动态规划的思想，将两点的最短路径问题隔离考虑。

首先假设其他结点之间的最短距离已经知道，只考虑从一个结点到另外一个结点的最短路径，很容易想到就是找出这两个结点之间的所有路径，比较他们谁最小，最小的无疑就是最短的那一条路径。

所以问题就变成了如何找到两结点之间的所有路径。我们的前提是其他结点之间的路径均为最短，所以很容易想到除了两结点的直接路径外，还有$f[x][y]=f[x][k]+f[k][y]$，其中f[x][y]表示从结点x到结点y的距离大小，意思就是从结点x到结点y之间除了直接到达的路径外，还可以经过k结点“绕一圈”到达。

至于为什么只绕一个其他结点，如将$f[x][k]=f[x][j]+f[j][k]$，即在x结点到k结点间绕到j结点到达，那么这样的路径一定比f[x][k]长，原因是其他的结点之间的距离都是最短的，那么f[x][k]最短已经是前提了。

所以我们可以得到一个公式
$$
f[x][y] = min(f[x][y], f[x][k]+f[k][y])
$$
通过这个公式就可以得到每个结点间的最短路径。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;

// 定义无穷大为0x3f3f3f3f作为min的初值
#define INF 0x3f3f3f3f

//打印矩阵函数，方便查看矩阵数据
void printM(vector< vector<int> > &m){
	printf("\n********************\n");
	for(int i = 0; i < m.size(); i++){
		for(int j = 0; j < m.size(); j++){
			if(m[i][j] == INF)
				printf("%-3s ","INF");
			else
				printf("%-3d ", m[i][j]);
		}
		printf("\n");
	}
}
int main(){
	int count;
	// 5 2 3 -1 -1 6 4 -1 12 15 20
	scanf("%d", &count);
	vector< vector<int> > m(count, vector<int>(count, 0));
	for(int i = 0; i < count; i++){
		for(int j = i + 1; j < count; j++){
			int num;
			scanf("%d", &num);
			if(num < 0){
                // 输入负数表示无穷大，可以任意定义
				num = INF;
			}
			m[i][j] = num;
			m[j][i] = num;
		}
	}
	printM(m);
    
    //算法核心
	for(int k = 0; k < count; k++){
		for(int x = 0; x < count; x++){
			for(int y = 0; y < count; y++){
				m[x][y] = min(m[x][y], m[x][k] + m[k][y]);
			}
		}
		printf("\nk = %d",k);
		printM(m);
	}
	int x, y;
	scanf("%d %d", &x, &y);
	printf("\n%d",m[x][y]);
}

核心代码

1
2
3
4
for(int k = 0; k < count; k++)
    for(int x = 0; x < count; x++)
        for(int y = 0; y < count; y++)
            m[x][y] = min(m[x][y], m[x][k] + m[k][y]);

存在问题

  • 为什么能保证公式中$f[x][k]$和$f[k][y]$为最短路径

    为了能够使用动态规划，将问题拆分成局部问题来解决，我们假设了一个前提就是$f[x][k]$和$f[k][y]$为最短路径，可是为什么就可以直接这样使用？

    没有找到相关文章博客，以下是我自己的证明：

    根据公式$f[x][y] = min(f[x][y], f[x][k]+f[k][y])$，其中k != x, k != y。可以知道当对于一个有n个结点的图来说，很容易得知k <= n，而k = n，即k的最后一次循环后就可以得到最短的路径，所以证明f[x][y]最短的问题就可以转化成证明f[x][n]和f[n][y]最短并与f[x][y]比较。

    同理，证明f[x][n]和f[n][y]最短就同等于证明最后一次循环得出的路径最短。例如f[x][n]带入上述公式$f[x][n] = min(f[x][n], f[x][k]+f[k][n])$，可以得出当k = n - 1时为最后一次循环得到最短路径，所以证明f[x][n]最短的问题就转化成证明f[x][n - 1]和f[n - 1][n]最短并与f[x][n]比较。并且知道这次调用公式的语句一定是在上面调用之前的。

    …

    所以根据数学归纳法，反过来看每次调用的f[x][k]和f[k][y]都已经是从下向上层层比较出来的最短值，可能不是最终的最短值但是一定是当前最短，所以推出的f[x][y]也一定是当前最短，当对比完所有的结点后就能保证是整张图最短的路径。

参考：

https://oi-wiki.org/graph/shortest-path/#floyd