用C语言编写Floyd算法求解最短路径

本文提供了一个用C语言编写的Floyd算法代码，用于计算图中任意两点之间的最短路径，并包含路径上的中间顶点。该代码简洁高效，易于理解，并附带一个实例说明算法的应用。

代码实现

#include <stdio.h>
#define INF 99999
#define MAX 100

int graph[MAX][MAX], path[MAX][MAX], n;

void printPath(int i, int j) {
    if (path[i][j] == -1) {
        printf("%d ", j);
        return;
    }
    printPath(i, path[i][j]);
    printPath(path[i][j], j);
}

void floyd() {
    int i, j, k;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            path[i][j] = -1;
        }
    }
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (graph[i][k] + graph[k][j] < graph[i][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

int main() {
    int i, j;
    printf("Enter the number of vertices: ");
    scanf("%d", &n);
    printf("Enter the adjacency matrix:
");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
            if (graph[i][j] == 0) {
                graph[i][j] = INF;
            }
        }
    }
    floyd();
    printf("The shortest paths between every pair of vertices:
");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (graph[i][j] == INF) {
                printf("- ");
            } else {
                printf("%d ", graph[i][j]);
            }
        }
        printf("\n");
    }
    printf("The shortest path between vertex 1 and vertex 5:
");
    printPath(0, 4);
    return 0;
}

算法输入与输出

• 输入： 一个n*n的矩阵，表示图的邻接矩阵，其中0表示无穷大或者不存在的边。
• 输出： 任意两个顶点之间的最短路径和路径上的中间顶点。

示例说明

假设有如下的5个顶点的图：

    1
  /   \
 2     3
  \   /
   4-5

邻接矩阵为：

0 2 4 0 0
2 0 0 1 0
4 0 0 3 0
0 1 3 0 1
0 0 0 1 0

运行程序后，输出为：

The shortest paths between every pair of vertices:
0 2 4 3 4 
2 0 6 1 2 
4 6 0 3 4 
3 1 3 0 1 
4 2 4 1 0 
The shortest path between vertex 1 and vertex 5:
1 4 5 

其中第一行为1到其他点的最短路径长度，第二行为2到其他点的最短路径长度，依此类推。最后一行为1到5的最短路径，经过的中间点为4。

总结

本文提供了一个用C语言编写的Floyd算法代码，用于计算图中任意两点之间的最短路径，并包含路径上的中间顶点。该代码简洁高效，易于理解，并附带一个实例说明算法的应用。希望本文对您理解和应用Floyd算法有所帮助。