Bellman-Ford算法C++

Bellman-Ford算法是一种用于图中寻找最短路径的算法，可以处理带有负权边的情况。下是一个用C++实现Bellman-Ford算法的示例代码：

#include <iostream>
#include <vector>
#include <limits>

#define INF std::numeric_limits<int>::max()

struct Edge {
    int from;
    int to;
    int weight;
};

void bellmanFord(std::vector<Edge>& edges, int n, int start, std::vector<int>& dist) {
    dist.resize(n, INF);
    dist[start] = 0;
    
    for (int i = 0; i < n - 1; ++i) {
        for (const auto& edge : edges) {
            int u = edge.from;
            int v = edge.to;
            int weight = edge.weight;
            
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }
    
    // 检测是否存在负权环
    for (const auto& edge : edges) {
        int u = edge.from;
        int v = edge.to;
        int weight = edge.weight;
        
        if (dist[u] != INF && dist[u] + weight < dist[v]) {
            std::cout << "图中存在负权环" << std::endl;
            return;
        }
    }
}

int main() {
    int n = 5; // 图中节点的数量
    std::vector<Edge> edges;
    
    // 添加图的边
    edges.push_back({0, 1, 6});
    edges.push_back({0, 3, 7});
    edges.push_back({1, 2, 5});
    edges.push_back({1, 3, 8});
    edges.push_back({1, 4, -4});
    edges.push_back({2, 1, -2});
    edges.push_back({3, 2, -3});
    edges.push_back({3, 4, 9});
    edges.push_back({4, 0, 2});
    edges.push_back({4, 2, 7});
    
    int start = 0; // 起始节点
    
    std::vector<int> dist;
    bellmanFord(edges, n, start, dist);
    
    // 输出最短路径
    for (int i = 0; i < n; ++i) {
        std::cout << "从节点" << start << "到节点" << i << "的最短距离为：" << dist[i] << std::endl;
    }
    
    return 0;
}

这段代码实现了Bellman-Ford算法，并输出了从指定起始节点到每个节点的最短距离。你可以根据自己的需求修改图的边和起始节点来运行并验证算法的正确性。注意，如果图中存在负权环，算法将无法给出正确结果，并会输出存在负权环的提示。