弗洛伊德算法

弗洛伊德算法 Floyd Algorithm

Floyd 算法运用了动态规划的思想，该算法用于求解所有顶点对之间的最短路径问题。Floyd 算法适用于带权有向图，可以处理负权重边，但不能处理图中含有负权重环的情况。

Floyd l算法通过三重循环迭代地更新最短路径。设定一个二维矩阵 $Dis$，其中 $Dis_{i, j}$ 表示从顶点 $i$ 到顶点 $j$ 的最短路径权重。初始时，将直接相连的顶点的距离设置为边的权重，没有直接连接的顶点距离设为无穷大，顶点到自身的距离设为 $0$。

该算法的核心思想是，检查每一对顶点 $(i, j)$ 是否可以通过另一个顶点 $k$（作为中转节点） 使得从 $i$ 节点到 $j$ 节点的路径更优。如果通过 $k$ 可以使路径更短，则更新 $Dis_{i, j}$。

因此可以得到状态转移方程：$Dis_{i, j} = \min(Dis_{i, k} + Dis_{k, j}, Dis_{i, j})$。

综上所述，Floyd 的代码如下（对应例题：洛谷 - B3647 【模板】Floyd）：

#include <iostream>
#define int long long
using namespace std;

int n, m, dis[105][105];

void init(){
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            dis[i][j] = 2147483647;
        }
        dis[i][i] = 0;
    }
    return ;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;

    init();  // 初始化。

    // 读入数据与建图。
    for (int i=1, u, v, w; i<=m; i++){
        cin >> u >> v >> w;
        dis[u][v] = dis[v][u] = min(dis[u][v], w);
    }

    // 进行动态规划。
    for (int k=1; k<=n; k++){
        for (int i=1; i<=n; i++){
            for (int j=1; j<=n; j++){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }

    // 输出最短路。
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            cout << dis[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

Floyd 算法的时间复杂度在 $O(N^3)$，其中 $N$ 表示图中顶点的数量。因此该算法的执行效率是极其低的，在没有特殊情况下，尽量避免使用该算法。但如果遇到多源最短路径的题目，Floyd 算法还是首选方案。