搜索与图论2.2-Floyd算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了搜索与图论2.2-Floyd算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、简述

\(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\)，那么就相当于每次都增加一个顶点，因此此问题可以逆向为按照给点的顺序依次增加顶点，计算图中已有顶点之间的最短路的距离和。
在顶点的增加中，利用布尔数组来表示某一顶点是否在图中，在计算最短路距离和的时候需要考虑当前的顶点是否在图中。文章来源地址https://www.toymoban.com/news/detail-711547.html

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

到了这里，关于搜索与图论2.2-Floyd算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！