如何用C语言实现Bellman-Ford（BF）最短路径算法？

贝尔曼-福特（Bellman-Ford）算法是一种用于寻找有向图中从源节点到其他所有节点的最短路径的动态规划算法。虽然C语言本身并没有内置的数据结构如Python那样方便，但我们可以手动模拟数组和循环来实现它。以下是简单的步骤：

1. 初始化：创建一个长度为V（节点数）的一维数组dist，其中dist[i]表示从源节点到节点i的最短距离。初始时，将dist[source]设为0，其余值设为无穷大。

2. V-1次松弛操作：对每条边（u, v），如果dist[u] + weight(u, v) < dist[v]，则更新dist[v]为dist[u] + weight(u, v)，这里weight(u, v)表示边(u, v)的权重。这是找出是否存在更短路径的过程。

3. 验证负权环：再做一次松弛操作，这次不论是否能缩短距离都进行。如果没有改变，则说明图中不存在负权环；如果有改变，那么存在负权环，并且无法确定最短路径。

下面是伪代码形式：

void bellman_ford(int graph[V][V], int src, int V, int dist[]) {
    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] != 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] != INF && dist[u] + graph[u][v] < dist[v]) {
                printf("Graph contains negative weight cycle.\n");
                return;
            }
        }
    }
}