用C语言完成给定1个源点,求其到其余结点的最短路径。结点个数需要运行时给出
时间: 2024-03-17 09:44:45 浏览: 28
可以使用 Dijkstra 算法或者 Bellman-Ford 算法来解决这个问题。
以下是使用 Dijkstra 算法的实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_NODES 1000
int graph[MAX_NODES][MAX_NODES];
int dist[MAX_NODES];
int visited[MAX_NODES];
int main() {
int n, src, i, j, min_dist, min_node;
printf("Enter the number of nodes: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
printf("Enter the source node: ");
scanf("%d", &src);
for (i = 0; i < n; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[src] = 0;
for (i = 0; i < n-1; i++) {
min_dist = INT_MAX;
for (j = 0; j < n; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
min_node = j;
}
}
visited[min_node] = 1;
for (j = 0; j < n; j++) {
if (graph[min_node][j] && !visited[j] && dist[min_node] != INT_MAX && dist[min_node]+graph[min_node][j] < dist[j]) {
dist[j] = dist[min_node] + graph[min_node][j];
}
}
}
printf("Shortest distances from node %d:\n", src);
for (i = 0; i < n; i++) {
printf("To node %d: %d\n", i, dist[i]);
}
return 0;
}
```
这个程序使用了一个邻接矩阵来表示图,输入时需要手动输入。第一行输入节点数,接下来输入邻接矩阵。最后输入源节点,程序会输出源节点到其他节点的最短距离。