用c语言实现：floyd算法求无向图的最短路径，并输出最短路径过程及其长度

以下是使用C语言实现Floyd算法求无向图最短路径的示例代码：

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

int graph[MAX_VERTICES][MAX_VERTICES];
int D[MAX_VERTICES][MAX_VERTICES];
int path[MAX_VERTICES][MAX_VERTICES];

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

void printPath(int start, int end) {
    printf("%d ", start);
    while (start != end) {
        start = path[start][end];
        printf("%d ", start);
    }
}

int main() {
    int n, m, i, j, u, v, w, start, end;

    printf("Enter the number of vertices: ");
    scanf("%d", &n);
    printf("Enter the number of edges: ");
    scanf("%d", &m);

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (i == j) {
                graph[i][j] = 0;
            }
            else {
                graph[i][j] = INF;
            }
        }
    }

    for (i = 0; i < m; i++) {
        printf("Enter the edge (u, v) and weight w: ");
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v] = w;
        graph[v][u] = w;
    }

    printf("Enter the start and end vertices: ");
    scanf("%d%d", &start, &end);

    floyd(n);

    printf("The shortest distance between %d and %d is %d\n", start, end, D[start][end]);
    printf("The shortest path is: ");
    printPath(start, end);

    return 0;
}

输入格式为：

Enter the number of vertices: [顶点数]
Enter the number of edges: [边数]
Enter the edge (u, v) and weight w: [起点] [终点] [权重]
...
Enter the start and end vertices: [起点] [终点]

例如，对于下面的无向图：

      4
  (0)---(1)
   | \   |
   |   \ | 6
   |   / |
  3| /   |
   |/    |
  (2)---(3)
      5

可以这样输入：

Enter the number of vertices: 4
Enter the number of edges: 5
Enter the edge (u, v) and weight w: 0 1 4
Enter the edge (u, v) and weight w: 0 2 3
Enter the edge (u, v) and weight w: 1 2 6
Enter the edge (u, v) and weight w: 1 3 6
Enter the edge (u, v) and weight w: 2 3 5
Enter the start and end vertices: 0 3

输出结果为：

The shortest distance between 0 and 3 is 8
The shortest path is: 0 2 3