C语言弗洛伊德算法求最短路径

C语言中的弗洛伊德算法（Floyd-Warshall algorithm）是一种用于求解图中所有节点之间最短路径的算法。它可以处理有向图或无向图，但不能处理带有负权边的图。

该算法的基本思想是通过动态规划的方式逐步更新节点之间的最短路径。算法的核心是一个二维数组，称为距离矩阵（distance matrix），用于存储任意两个节点之间的最短路径长度。

以下是C语言中弗洛伊德算法的基本实现步骤：

1. 初始化距离矩阵：将所有节点之间的距离初始化为无穷大（表示不可达），将自身到自身的距离初始化为0。
2. 遍历图中的每个边，更新距离矩阵：如果存在一条边 (u, v) 的权重为 w，且从节点 u 到节点 v 的距离大于从节点 u 经过节点 k 再到节点 v 的距离（即 distance[u][v] > distance[u][k] + distance[k][v]），则更新距离矩阵中的值为 distance[u][k] + distance[k][v]。
3. 重复步骤2，直到遍历完所有节点和边。
4. 最终得到的距离矩阵即为图中任意两个节点之间的最短路径长度。

下面是一个简单的C语言代码示例：

#include <stdio.h>

#define INF 99999
#define V 4

void floydWarshall(int graph[V][V]) {
    int distance[V][V];
    int i, j, k;

    // 初始化距离矩阵
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            distance[i][j] = graph[i][j];
        }
    }

    // 更新距离矩阵
    for (k = 0; k < V; k++) {
        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                if (distance[i][k] + distance[k][j] < distance[i][j]) {
                    distance[i][j] = distance[i][k] + distance[k][j];
                }
            }
        }
    }

    // 打印最短路径长度
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if (distance[i][j] == INF) {
                printf("INF ");
            } else {
                printf("%d ", distance[i][j]);
            }
        }
        printf("\n");
    }
}

int main() {
    int graph[V][V] = {
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0}
    };

    floydWarshall(graph);

    return 0;
}

这段代码中，我们使用一个4x4的矩阵表示图的邻接矩阵，其中INF表示不可达的情况。运行代码后，将输出图中任意两个节点之间的最短路径长度。