Floyd 算法

01 Dec 2024

1. 简介

Floyd 算法用于求图中任意两个顶点之间的最短距离，因此也叫多源最短路算法。它适合顶点数量较少、但需要查询很多对顶点最短距离的情况。

算法使用二维数组 dist 保存距离，其中 dist[i][j] 表示从 i 到 j 的当前最短距离。因为要保存所有点对之间的距离，空间复杂度是 O(n²)；三重循环会带来 O(n³) 的时间复杂度，所以通常适用于 n 在几百以内的图。

2. 核心思路

一开始，dist[i][j] 只记录 i 到 j 的直接边权。如果 i 和 j 没有直接边，就把距离设为一个足够大的数；每个点到自己的距离为 0。

接着依次允许 1 到 n 号点成为中转点。假设当前允许 k 作为中转点，那么从 i 到 j 有两种选择：

不经过 k，距离仍是 dist[i][j]。
经过 k，距离是 dist[i][k] + dist[k][j]。

取这两种距离中的较小值，就得到新的 dist[i][j]：

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]);

最外层必须是中转点 k。这样第 k 轮结束时，所有最短路都只会使用 1 到 k 号点作为中转点，状态才是完整的。

3. 例子：多次最短路查询

给定一个无向带权图，读入道路后需要回答多次“从 x 到 y 的最短距离”查询。先运行一次 Floyd，之后每次查询直接输出 dist[x][y] 即可。

#include <bits/stdc++.h>
using namespace std;

const long long INF = (long long)4e18;
long long dist[510][510];
int n, m;

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dist[i][j] = (i == j ? 0 : INF);
        }
    }

    while (m--) {
        int x, y;
        long long w;
        cin >> x >> y >> w;
        dist[x][y] = min(dist[x][y], w);
        dist[y][x] = min(dist[y][x], w);
    }

    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 q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;

        if (dist[x][y] == INF) cout << -1 << '\n';
        else cout << dist[x][y] << '\n';
    }
    return 0;
}

例如，若道路为 1 - 2（权值 2）、2 - 3（权值 3）、1 - 3（权值 10）、3 - 4（权值 1），那么 1 到 4 的最短距离是 6，对应路线为 1 → 2 → 3 → 4。

Floyd 适合“任意两点之间都可能查询”的小规模图。若图很大、只需要一个起点到其他点的最短路，并且边权非负，通常应考虑 Dijkstra 算法。Floyd 也要求图中不存在可达的负环，否则最短距离没有确定的有限值。

Floyd 算法

Related Posts