floyd算法c语言实现

下面是Floyd算法的C语言实现：

#include <stdio.h>
#define INF 99999

void floyd(int n, int graph[][n]) {
    int dist[n][n];
    int i, j, k;

    // 初始化邻接矩阵
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // 通过中间顶点k寻找更短的路径
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    // 打印最短路径
    printf("最短路径矩阵:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (dist[i][j] == INF)
                printf("INF ");
            else
                printf("%d ", dist[i][j]);
        }
        printf("\n");
    }
}

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

    floyd(n, graph);

    return 0;
}

上述代码中，我们首先将邻接矩阵作为参数传递给floyd函数。在函数中，我们使用邻接矩阵初始化一个dist矩阵，其中dist[i][j]表示从顶点i到顶点j的最短路径长度。然后，我们使用三重循环遍历所有顶点，以中间顶点k为跳板，寻找更短的路径。最后，我们打印最短路径矩阵。

在上面的代码中，我们假设顶点编号从0到n-1。如果要处理其他编号，只需将代码中的n和graph数组更改为适当的值即可。