C语言实现单源点最短路径,测试输入:7 v1 v2 10 v2 v3 50 v3 v4 20 v3 v5 10 v4 v5 60 v1 v5 100 v1 v4 30 预期输出:v1 0 v2 10 v4 30 v3 50 v5 60
时间: 2024-05-07 17:19:19 浏览: 45
C语言实现单源路径、多级调度、最小生成树
以下是使用 Dijkstra 算法实现单源点最短路径的 C 语言代码,可以实现你所需的功能:
```c
#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define MAXN 1005
int n, m; // n是节点数,m是边数
int graph[MAXN][MAXN]; // 图的邻接矩阵表示
int dist[MAXN]; // 存储源点到各个节点的最短距离
int vis[MAXN]; // 标记节点是否已经确定最短路径
char name[MAXN][10]; // 节点的名称,用于输出
// Dijkstra算法求解单源点最短路径
void dijkstra(int s) {
memset(vis, 0, sizeof(vis));
memset(dist, INF, sizeof(dist));
dist[s] = 0;
for (int i = 0; i < n; i++) {
int min_dist = INF, u;
for (int j = 1; j <= n; j++) {
if (!vis[j] && dist[j] < min_dist) {
u = j;
min_dist = dist[j];
}
}
vis[u] = 1;
for (int v = 1; v <= n; v++) {
if (!vis[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
int main() {
scanf("%d", &m);
int k = 0;
for (int i = 1; i <= m; i++) {
char s[10], t[10];
int w;
scanf("%s %s %d", s, t, &w);
int u, v;
for (int j = 1; j <= k; j++) {
if (strcmp(name[j], s) == 0) {
u = j;
break;
}
}
if (u == 0) {
k++;
u = k;
strcpy(name[u], s);
}
for (int j = 1; j <= k; j++) {
if (strcmp(name[j], t) == 0) {
v = j;
break;
}
}
if (v == 0) {
k++;
v = k;
strcpy(name[v], t);
}
graph[u][v] = graph[v][u] = w;
}
n = k;
dijkstra(1);
for (int i = 1; i <= n; i++) {
printf("%s %d\n", name[i], dist[i]);
}
return 0;
}
```
需要注意的是,代码中使用邻接矩阵表示图,节点的名称使用字符串存储,并且需要在输入时先将名称转换为对应的编号。输出时需要根据编号找到对应的名称输出。
阅读全文