Floyd算法C++

Floyd算法，也称为插点法，是解决任意两点间的最短路径的一种算法，可以用于有向图或者有负权边的图。它采用动态规划的思想，通过对每两个顶点之间的所有顶点作为中介点，求出它们之间的最短路径，从而得到任意两个顶点之间的最短路径。Floyd算法的时间复杂度为O(n^3)。

以下是Floyd算法的C++代码实现：

#include <iostream>
using namespace std;

const int maxn = 100;
const int inf = 0x3f3f3f3f;

int n, m;  // n表示顶点数，m表示边数
int dist[maxn][maxn];  // 存储每两个顶点之间的距离

void Floyd() {
    // 初始化距离矩阵
    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;
        }
    }
    
    // 输入每个边的权值
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = w;
    }

    // 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;
    Floyd();
    return 0;
}