代码随想录算法训练营第五十九天|Day59 图论

https://www.programmercarl.com/kamacoder/0094.%E5%9F%8E%E5%B8%82%E9%97%B4%E8%B4%A7%E7%89%A9%E8%BF%90%E8%BE%93I.html

思路

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>#define MAXM 10000 // 假设最大边数为10000
#define MAXN 1000  // 假设最大节点数为1000typedef struct {int from; // 边的起点int to;   // 边的终点int weight; // 边的权重
} Edge;int main() {int n, m, p1, p2, val;scanf("%d %d", &n, &m);Edge edges[MAXM]; // 用于存储所有的边for(int i = 0; i < m; i++) {scanf("%d %d %d", &p1, &p2, &val);edges[i].from = p1;edges[i].to = p2;edges[i].weight = val; // 建立边}int start = 1; // 起点int end = n;   // 终点// 存储从起点到每个节点的最短距离int minDist[MAXN];for (int i = 1; i <= n; i++) {minDist[i] = INT_MAX; // 初始化为无穷大}minDist[start] = 0; // 起点到本身的距离为0// 对所有边进行松弛 n-1 次for (int i = 1; i < n; i++) {for (int j = 0; j < m; j++) {// 松弛操作if (minDist[edges[j].from] != INT_MAX && minDist[edges[j].to] > minDist[edges[j].from] + edges[j].weight) {minDist[edges[j].to] = minDist[edges[j].from] + edges[j].weight;}}}// 输出结果if (minDist[end] == INT_MAX) {printf("unconnected\n"); // 不能到达终点} else {printf("%d\n", minDist[end]); // 到达终点最短路径}return 0;
}

学习反思

代码实现了使用Dijkstra算法求解单源最短路径问题。代码中的Edge结构体表示一条边，包括起点、终点和权重。首先从输入中读取节点数n和边数m，然后通过循环读取每条边的信息，并保存到edges数组中。接下来定义了起点start和终点end，以及minDist数组用于存储从起点到每个节点的最短距离。然后，使用嵌套循环对所有边进行n-1次松弛操作，以更新minDist数组中的最短距离。最后，判断终点的最短距离是否为INT_MAX，如果是则输出"unconnected"，否则输出最短距离。整个代码的时间复杂度为O(nm)。