【PTA数据结构 | C语言版】求单源最短路的Dijkstra算法

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

题目

请编写程序，实现在带权的有向图中求单源最短路的 Dijkstra 算法。
注意：当多个待收录顶点路径等长时，按编号升序进行收录。

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

输出格式：
参考样例。按顶点编号的升序，每行输出一个顶点的信息，格式为：

v[i]: dist=x, path=y

其中 i 为顶点编号；x 为顶点 0 到顶点 i 的最短距离；y 为对应的最短路径上，i 的前驱顶点编号。因为起点 0 没有前驱顶点，所以对应的 y 记为 -1。

输入样例：
6 9
0 1 1
0 2 12
1 2 9
1 3 3
2 4 5
3 2 4
3 4 13
3 5 15
4 5 4

输出样例：
v[0]: dist=0, path=-1
v[1]: dist=1, path=0
v[2]: dist=8, path=3
v[3]: dist=4, path=1
v[4]: dist=13, path=2
v[5]: dist=17, path=4

代码

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>#define MAX_VERTEX 100    // 最大顶点数
#define INF INT_MAX       // 表示无穷大int main() {int n, m;scanf("%d %d", &n, &m);// 初始化邻接矩阵，全部设为无穷大int graph[MAX_VERTEX][MAX_VERTEX];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {graph[i][j] = INF;}}// 读取边信息并填充邻接矩阵for (int i = 0; i < m; i++) {int u, v, w;scanf("%d %d %d", &u, &v, &w);graph[u][v] = w;  // 有向边，只设置一个方向}// Dijkstra算法所需数组int dist[MAX_VERTEX];   // 存储从源点到各顶点的最短距离int path[MAX_VERTEX];   // 存储最短路径上各顶点的前驱int collected[MAX_VERTEX];  // 标记顶点是否已收录// 初始化for (int i = 0; i < n; i++) {dist[i] = graph[0][i];  // 初始距离为源点(0)到i的直接距离if (dist[i] < INF) {path[i] = 0;        // 有直接路径，前驱为源点} else {path[i] = -1;       // 无直接路径，前驱为-1}collected[i] = 0;       // 所有顶点初始均未收录}// 源点自身初始化dist[0] = 0;path[0] = -1;collected[0] = 1;// 主循环：每次收录一个顶点，共收录n-1个（源点已收录）for (int i = 0; i < n - 1; i++) {// 步骤1：找出未收录顶点中dist最小的顶点vint min_dist = INF;int v = -1;for (int j = 0; j < n; j++) {if (!collected[j]) {// 当距离相等时，选择编号较小的顶点（天然满足，因按编号遍历）if (dist[j] < min_dist) {min_dist = dist[j];v = j;}}}// 若没有可收录的顶点（图不连通），提前退出if (v == -1) break;// 步骤2：收录顶点vcollected[v] = 1;// 步骤3：更新所有未收录的邻接顶点的dist和pathfor (int w = 0; w < n; w++) {// 若w未收录且v到w有边if (!collected[w] && graph[v][w] < INF) {// 若经过v到w的路径更短if (dist[v] + graph[v][w] < dist[w]) {dist[w] = dist[v] + graph[v][w];path[w] = v;}}}}// 按顶点编号升序输出结果for (int i = 0; i < n; i++) {printf("v[%d]: dist=%d, path=%d\n", i, dist[i], path[i]);}return 0;
}