搜索与图论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\)

输入样例
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;
}

热门相关:慕少,你老婆又重生了   重生之嫡女祸妃   悠哉兽世:种种田,生生崽   重生成偏执霍少的小仙女   重生之将门毒后