用C语言编程实现Dijkstra算法,给出源代码和运行结果截图。
时间: 2024-02-11 11:06:17 浏览: 77
zuiduanlujing.rar_C语言 最短路径_最短路径c-c
很抱歉,作为AI,我无法提供截图功能。不过,以下是使用C语言实现Dijkstra算法的源代码,您可以尝试在本地编译运行并查看结果:
```c
#include <stdio.h>
#include <stdbool.h>
#define INF 0x3f3f3f3f
int n, m; // 图的节点数和边数
int edge[1001][1001]; // 保存边的权重
int dis[1001]; // 保存起点到每个节点的最短路径长度
bool vis[1001]; // 标记节点是否已经被扩展过
// 找到当前未被扩展的距离起点最近的节点
int find_min_node() {
int min_dis = INF, min_node = -1;
for (int i = 1; i <= n; i++) {
if (!vis[i] && dis[i] < min_dis) {
min_dis = dis[i];
min_node = i;
}
}
return min_node;
}
void dijkstra(int s) {
// 初始化
for (int i = 1; i <= n; i++) {
dis[i] = INF;
vis[i] = false;
}
dis[s] = 0;
// 扩展n次,即每个节点都被扩展过一次
for (int i = 1; i <= n; i++) {
int u = find_min_node();
vis[u] = true;
// 更新与u相邻的节点的最短路径长度
for (int v = 1; v <= n; v++) {
if (!vis[v] && edge[u][v] != INF && dis[u] + edge[u][v] < dis[v]) {
dis[v] = dis[u] + edge[u][v];
}
}
}
}
int main() {
printf("请输入节点数和边数:\n");
scanf("%d%d", &n, &m);
// 初始化边的权重为INF
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
edge[i][j] = INF;
}
}
// 读入边的权重
printf("请输入每条边的起点、终点和权重:\n");
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edge[u][v] = edge[v][u] = w;
}
// 求起点到每个节点的最短路径长度
dijkstra(1);
// 输出结果
printf("起点到每个节点的最短路径长度为:\n");
for (int i = 1; i <= n; i++) {
printf("%d ", dis[i]);
}
printf("\n");
return 0;
}
```
在本地编译运行后,输入节点数和边数,输入每条边的起点、终点和权重,程序将输出起点到每个节点的最短路径长度。
阅读全文