一、简述
\(Floyd\) 算法是一种可以快速求解图上所有顶点之间最短路径的算法。
\(Bellman-Ford\) 和 \(Dijkstra\) 算法求解的都是从一个起始点开始的最短路。如果想要求解图中所有顶点之间的最短路，就需要枚举每个点做为起点，这样十分低效。\(Floyd\) 算法(也称 \(Floyd-Warshall\) 算法)处理用邻接矩阵存储的有向图(无向图的一条边可以看做有向图的两条边)十分方便。
二、Floyd算法
memset(f, 127, sizeof f);
f[0][i][j] = a[i][j];
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
f[k][i][j] = min(f[k - 1][i][j], f[k - 1][i][k] + f[k - 1][k][j]);
- \(f[k][i][j]\) 表示从 \(i\) 到 \(j\) 并且可以经过 \(1\) 至 \(k\) 的最短路径，\(f[0][i][j]\) 表示从 \(i\) 到 \(j\) 并且不经过任何中间点的最短路径。
- \(a[i][j]\) 表示从 \(i\) 到 \(j\) 的边的长度，\(a[i][i]=0\)。
\(Floyd\) 算法是动态规划的思想。在转移方程中，从 \(i\) 到 \(j\) 的最短路径可以经过顶点 \(k\)，也可以不经过顶点 \(k\)，经过顶点 \(k\)，则 \(k\) 将路径分为两段，前后两段最多只能经过 \(1\) 至 \(k-1\)，不经过顶点 \(k\)，则最多经过 \(1\) 至 \(k-1\)。
那么上述代码可以空间优化吗？答案是肯定的，优化后的代码如下
memset(f, 127, sizeof f);
f[i][j] = a[i][j];
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (f[i][k] < 1 << 30 && f[k][j] < 1 << 30) // 注意int类型数据范围
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
优化后，验证一下正确性，在加入顶点 \(k\) 之前，\(f[i][j]\) 就相当于 \(f[k-1][i][j]\)，但是 \(f[i][k]\) 以及 \(f[k][j]\) 是有可能在 \(f[i][j]\) 之前被覆盖的，但是注意 \(f[k][i][j]\) 的含义为从 \(i\) 到 \(j\) 并且可以经过 \(1\) 至 \(k\) 的最短路径，那么 \(1\) 至 \(k\) 为中间点，则 \(f[k-1][i][k]=f[k][i][k]\) 并且 \(f[k-1][k][j]=f[k][k][j]\)，因此可以使用 \(f[i][k] + f[k][j]\) 来替换。
关于路径的记录，可以使用 \(path\) 数组在距离更新时来记录，\(path[i][j]=k\)，表示从 \(i\) 到 \(j\) 经过中间点 \(k\)(path[i][j]=-1$ 表示 \(i\) 和 \(j\) 直接相连)，然后利用 \(k\) 将路径分为两部分，依次递归输出。
模板题AcWing854.Floyd求最短路
题目描述
给定一个 \(n\) 个点 \(m\) 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 \(k\) 个询问，每个询问包含两个整数 \(x\) 和 \(y\)，表示查询从点 \(x\) 到点 \(y\) 的最短距离，如果路径不存在，则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 \(n,m,k\)。
接下来 \(m\) 行，每行包含三个整数 \(x,y,z\)，表示存在一条从点 \(x\) 到点 \(y\) 的有向边，边长为 \(z\)。
接下来 \(k\) 行，每行包含两个整数 \(x,y\)，表示询问点 \(x\) 到点 \(y\) 的最短距离。
输出格式
共 \(k\) 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。
数据范围
\(1≤n≤200\)，
\(1≤k≤n^2\)，
\(1≤m≤20000\)，
图中涉及边长绝对值均不超过 \(10000\)。
输入样例
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例
impossible
1
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, q;
int dist[N][N];
void floyd() {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
int main() {
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (i == j)
dist[i][j] = 0;
else
dist[i][j] = INF;
}
while (m--) {
int x, y, z;
cin >> x >> y >> z;
dist[x][y] = min(dist[x][y], z);
}
floyd();
while (q--) {
int x, y;
cin >> x >> y;
if (dist[x][y] > INF / 2)
puts("impossible");
else
cout << dist[x][y] << endl;
}
return 0;
}
三、Floyd算法的应用
这里给出一个和 \(Floyd\) 算法思想相关的题目。
Daimayuan Online Judge.删点游戏
题目描述
给你一张 \(n\) 个顶点的有向简单图，顶点编号从 \(1\) 到 \(n\)，我们要把所有顶点一个一个删完。小蜗每次会删掉图中的一个顶点和所有与它相连的边，小蜗想知道每删去一个顶点之后图中所有点对的距离之和。
输入格式
第一行一个整数 \(n\)，表示顶点数。
接下来 \(n\) 行，每行 \(n\) 个整数，组成一个 \(n×n\) 的矩阵 \(A\) 表示这张图的邻接矩阵，矩阵第 \(i\) 行第 \(j\) 列表示 \(i\) 号顶点到 \(j\) 号顶点有一条边权为 \(A[i][j]\) 的边。
接下来一行，输入 \(n\) 个数 \(x_1,x_2,...,x_n\)，代表删除顶点的顺序。
输出格式
输出一行 \(n\) 个数依次表示删除了第 \(0\) 个点（一个点都没删除）到第 \(n−1\) 个点（图中还剩下一个点）后，图中所有剩下的点对的距离之和。
数据范围
对于所有数据，保证 \(2≤n≤300,1≤A[i][j]≤10000,A[i][i]=0,1≤x_i≤n\)。
输入样例
2
0 5
4 0
1 2
输出样例
9 0
解题思路
根据题目描述，按照给定的顺序删除顶点，计算剩余各点之间的最短路的距离和。在 \(Floyd\) 算法中，在求解过程中是依次枚举中间点 \(k\)，那么就相当于每次都增加一个顶点，因此此问题可以逆向为按照给点的顺序依次增加顶点，计算图中已有顶点之间的最短路的距离和。
在顶点的增加中，利用布尔数组来表示某一顶点是否在图中，在计算最短路距离和的时候需要考虑当前的顶点是否在图中。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 310, M = 65;
typedef long long LL;
int n;
int x[N], dist[N][N];
bool b[N];
int a[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &dist[i][j]);
for (int i = 1; i <= n; i++)
scanf("%d", &x[i]);
for (int l = n; l; l--) {
int k = x[l];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
b[k] = true;
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (b[i] && b[j])
ans += dist[i][j];
a[l] = ans;
}
for (int i = 1; i <= n; i++)
printf("%d ", a[i]);
return 0;
}