BELLMAN-FORD代码

贝尔曼-福特（Bellman-Ford）算法是一种用于求解有向图中单源最短路径问题的动态规划算法。该算法特别适用于存在负权边的情况下，因为它可以处理负权重循环的情况，而Dijkstra算法在这种情况下无法正确工作。

1. **算法步骤**:
- 初始化：对所有顶点赋予从源顶点到它们的距离为无穷大，除了源顶点自身距离为0。
- V-1轮迭代：对于每一轮，更新每个顶点的最短路径。检查每条边 (u, v)，如果通过u可达v并且总代价（当前距离u加上边(u, v)的权重）小于v当前已知的距离，则更新v的距离。
- 检查负环：进行V次迭代后（其中V是顶点数量），如果没有进一步的更新发生，那么算法确定找到了最短路径。如果有，说明存在负权重循环。

2. **伪代码**（使用松弛操作表示）：

void bellmanFord(int graph[V][V], int src, int V)
{
    // 初始化距离数组
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;

    // 设置源节点的距离为0
    dist[src] = 0;

    // 进行V-1轮松弛操作
    for (int i = 0; i < V - 1; i++) {
        for (int u = 0; u < V; u++) {
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != INF && dist[u] + graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // 检查是否存在负权重环
    for (int u = 0; u < V; u++) {
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
                // 如果存在，则报告错误（因为已经进行了V-1轮）
                cout << "Graph contains a negative weight cycle!";
                return;
            }
        }
    }

    // 返回最短路径
    cout << "Vertex \t\tDistance from Source";
    for (int i = 0; i < V; i++)
        cout << "\n" << i << "\t\t" << dist[i];
}