【PTA数据结构 | C语言版】求所有点对间最短路的Floyd-Warshall算法

本专栏持续输出数据结构题目集，欢迎订阅。

题目

请编写程序，实现在带权有向图中求所有点对间最短路的 Floyd-Warshall 算法。

输入格式：
输入首先在第一行给出两个正整数，依次为当前要创建的图的顶点数 n（≤100）和边数 m。
随后 m 行，每行给出一条有向边的起点编号、终点编号、权重。顶点编号从 0 开始，权重（≤100）为正整数。同行数字均以一个空格分隔。

输出格式：
参考样例。首先第一行输出 dist:，随后逐行输出距离矩阵中存储的值；接下来一行输出 path:，随后逐行输出路径矩阵中存储的值。为简单起见，同行的每个数字后面都有一个空格。
注意：不连通的距离定义为 10^9；无中间顶点的路径值定义为 −1。

输入样例：
3 5
0 1 6
0 2 22
1 2 12
2 0 5
2 1 17

输出样例：
dist:
0 6 18
17 0 12
5 11 0
path:
-1 -1 1
2 -1 -1
-1 0 -1

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTICES 100
#define INF 1000000000

int main() {
    int n, m;
    int dist[MAX_VERTICES][MAX_VERTICES];
    int path[MAX_VERTICES][MAX_VERTICES];

    // 读取顶点数和边数
    scanf("%d %d", &n, &m);

    // 初始化距离矩阵和路径矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                dist[i][j] = 0;
                path[i][j] = -1;
            } else {
                dist[i][j] = INF;
                path[i][j] = -1;
            }
        }
    }

    // 读取每条边的信息
    for (int i = 0; i < m; i++) {
        int u, v, weight;
        scanf("%d %d %d", &u, &v, &weight);
        dist[u][v] = weight;
        path[u][v] = -1;
    }

    // Floyd-Warshall算法核心
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = k;
                }
            }
        }
    }

    // 输出距离矩阵
    printf("dist:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", dist[i][j]);
        }
        printf("\n");
    }

    // 输出路径矩阵
    printf("path:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", path[i][j]);
        }
        printf("\n");
    }

    return 0;
}