Floyd 最短路CSP-S

💡 核心思想

Floyd 算法求全源最短路——任意两点之间的最短距离。核心是一个简单的三重循环：枚举中转点 $k$，对每对 $(i,j)$ 尝试通过 $k$ 中转是否更短。虽然 $O(n^3)$ 的复杂度看起来很大，但代码极其简洁，$n \le 500$ 时完全可用。

🎯 直觉理解

Floyd 就像"搭桥"。一开始每对城市之间只有直飞的航班。然后一个一个城市地"开放中转"——开放第1个城市作为中转站后，有些城市对就可能找到更便宜的路线了（经过第1个城市转机）。依次开放所有城市，最终得到所有城市对的最短路径。

📝 算法流程

1. 初始化：dist[i][j] = 直接边的权，没有边则 INF
2. 三重循环：k 在最外层
3. 更新：$dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])$
4. 可同时求传递闭包

$$dist[i][j] = \min_{k=1}^{n}(dist[i][j], dist[i][k] + dist[k][j])$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    const int INF = 1e9;
    vector<vector<int>> dist(n+1, vector<int>(n+1, INF));
    for (int i = 1; i <= n; i++) dist[i][i] = 0;
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w); // 处理重边
    }
    for (int k = 1; k <= n; k++)        // 中转点 k 必须在最外层！
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << dist[i][j] << " ";
        cout << endl;
    }
    return 0;
}

⚠️ 常见坑点

📚 相关题目