C++写Bellman-Ford

下面是C++实现的Bellman-Ford算法代码：

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

struct Edge {
    int from, to, dist;
};

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n, m, s;                 // n是点数，m是边数，s是源点
int d[MAXN];                 // d[i]表示从源点s到i的最短距离
Edge edges[MAXN];            // 存储所有边的信息

void BellmanFord() {
    memset(d, INF, sizeof(d));          // 将所有点的距离初始化为INF
    d[s] = 0;                            // 将源点距离初始化为0
    for (int i = 1; i < n; i++) {        // 进行n-1轮松弛操作
        for (int j = 0; j < m; j++) {    // 枚举所有边
            int u = edges[j].from;
            int v = edges[j].to;
            int w = edges[j].dist;
            if (d[u] != INF && d[v] > d[u] + w) {
                d[v] = d[u] + w;         // 松弛操作
            }
        }
    }
}

int main() {
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        cin >> edges[i].from >> edges[i].to >> edges[i].dist;
    }
    BellmanFord();
    for (int i = 1; i <= n; i++) {
        if (d[i] == INF) {
            cout << "INF ";
        } else {
            cout << d[i] << " ";
        }
    }
    cout << endl;
    return 0;
}

该代码的时间复杂度为O(nm)，其中n和m分别表示点数和边数。在实际应用中，如果图中不存在负环，则算法会在n-1轮松弛操作后得到最短路径；如果存在负环，则算法会一直松弛下去，无法得到最短路径。