FLOYD

复杂度

Floyd-Warshall算法的时间复杂度为

O(|V|^{3})[4]，空间复杂度为

O(|V|^{2})，其中

V是点集。

原理

动态规划

适用范围

Floyd-Warshall 算法适用于解决带权有向图或带权无向图的全源最短路径问题，即计算任意两个顶点之间的最短路径长度。

Floyd-Warshall 算法的适用范围包括：

有向图或无向图：Floyd-Warshall 算法可以应用于有向图或无向图，可以处理带权边的情况。

正权边或负权边：Floyd-Warshall 算法可以处理正权边和负权边的情况。然而，如果图中存在负权环（环上的边权之和为负），则算法无法得到正确结果。

无需指定起点和终点：Floyd-Warshall 算法计算了任意两个顶点之间的最短路径长度，因此无需指定特定的起点和终点。

中心代码

for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (g[i][k] != INF && g[k][j] != INF && g[i][k] + g[k][j] < g[i][j])
                    g[i][j] = g[i][k] + g[k][j];
            }
        }
    }

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

const int INF = 10000000;

void floyd(vector<vector<int>>& g, int n, int m) {
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a][b] = w;
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (g[i][k] != INF && g[k][j] != INF && g[i][k] + g[k][j] < g[i][j])
                    g[i][j] = g[i][k] + g[k][j];
            }
        }
    }
}

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

    vector<vector<int>> g(n + 1, vector<int>(n + 1, INF));
    floyd(g, n, m);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j] == INF)
                cout << "NO";
            else
                cout << g[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}