搜索与图论2.2-Floyd算法

2023-10-15 19:08 由 Cocoicobird 发表于 #其他

一、简述

$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$。

输入样例

输出样例

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$。

输入样例

输出样例

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;
}