Bellman-Ford的c语言代码

Bellman-Ford算法是一种用于求解带权重的有向图中最短路径问题的动态规划算法。以下是使用C语言实现的一个简单版本：

#include <stdio.h>
#include <limits.h>

#define V 4 // 图的顶点数
#define INF INT_MAX // 定义最大边权值

void bellman_ford(int graph[V][V], int src) {
    int dist[V]; // 初始化所有节点距离为无穷大，除了源点
    for (int i = 0; i < V; i++) {
        dist[i] = INF;
    }
    dist[src] = 0; // 源点的距离设为0

    // 进行V-1次迭代，因为最短路径最多V-1步
    for (int i = 0; i < V - 1; i++) {
        for (int u = 0; u < V; u++) {
            // 对于每个节点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];
                }
            }
        }
    }

    // 再做一次检查，防止负权回路的存在
    bool negative_cycle = false;
    for (int u = 0; u < V; u++) {
        if (graph[u][src] != INF && dist[u] + graph[u][src] < dist[src]) {
            negative_cycle = true; // 如果找到一条更短路径，则存在负权回路
            break;
        }
    }

    if (!negative_cycle)
        printf("Shortest path from %d to all vertices are \n", src);
    else
        printf("Graph contains a negative weight cycle.\n");

    // 打印结果
    for (int i = 0; i < V; i++)
        printf("Distance from source to vertex %d is %d\n", i, dist[i]);
}

int main() {
    int graph[V][V] = {{0, -1, 4, INF},
                       {-1, 0, INF, 2},
                       {4, INF, 0, -3},
                       {INF, 2, -3, 0}};

    bellman_ford(graph, 0); // 从顶点0开始寻找最短路径
    return 0;
}

这里假设图已经存储在一个二维数组`graph`中，`graph[u][v]`表示从顶点`u`到顶点`v`的边权。注意这个代码只能处理负权边不超过V-1倍的情况，若存在负权回路则会检测到。