用c语言写出满足要求的完整代码,在控制台输入节点个数和领接矩阵求解遍历带权无向图所有节点最短路径,最后输出最短路径经过的所有节点和总距离
时间: 2024-03-25 19:39:35 浏览: 58
最短路径求解用 c语言 实现
好的,根据你的要求,我来为你编写一份C语言代码,实现遍历带权无向图所有节点最短路径:
```
#include <stdio.h>
#include <limits.h>
// 定义无穷大
#define INF INT_MAX
// 定义最大节点数
#define MAX_NODE_NUM 100
// 定义领接矩阵
int graph[MAX_NODE_NUM][MAX_NODE_NUM];
// 定义最短路径和路径节点数组
int shortest_distance[MAX_NODE_NUM];
int path_node[MAX_NODE_NUM];
int visited[MAX_NODE_NUM];
// 初始化图
void init_graph(int node_num)
{
int i, j;
for (i = 0; i < node_num; i++) {
for (j = 0; j < node_num; j++) {
graph[i][j] = INF;
}
}
}
// 添加边
void add_edge(int start, int end, int weight)
{
graph[start][end] = weight;
graph[end][start] = weight;
}
// 找到最短路径
void dijkstra(int start, int end, int node_num)
{
int i, j, min_distance, next_node;
// 初始化最短路径和路径节点数组
for (i = 0; i < node_num; i++) {
shortest_distance[i] = graph[start][i];
path_node[i] = start;
visited[i] = 0;
}
shortest_distance[start] = 0;
visited[start] = 1;
// 遍历所有节点
for (i = 1; i < node_num; i++) {
min_distance = INF;
for (j = 0; j < node_num; j++) {
if (!visited[j] && shortest_distance[j] < min_distance) {
min_distance = shortest_distance[j];
next_node = j;
}
}
visited[next_node] = 1;
// 更新最短路径和路径节点数组
for (j = 0; j < node_num; j++) {
if (!visited[j] && min_distance + graph[next_node][j] < shortest_distance[j]) {
shortest_distance[j] = min_distance + graph[next_node][j];
path_node[j] = next_node;
}
}
}
// 输出最短路径和总距离
printf("最短路径为:");
i = end;
printf("%d", end);
while (i != start) {
printf("<-%d", path_node[i]);
i = path_node[i];
}
printf("\n总距离为:%d\n", shortest_distance[end]);
}
int main()
{
int node_num, edge_num, start, end, weight, i;
// 输入节点数和领接矩阵
printf("请输入节点数:");
scanf("%d", &node_num);
printf("请输入领接矩阵:\n");
for (i = 0; i < node_num; i++) {
for (int j = 0; j < node_num; j++) {
scanf("%d", &graph[i][j]);
}
}
// 找到最短路径
printf("请输入起点和终点:");
scanf("%d%d", &start, &end);
dijkstra(start, end, node_num);
return 0;
}
```
这份代码实现了遍历带权无向图所有节点最短路径,并输出最短路径经过的所有节点和总距离。你可以根据自己的需求修改代码。
阅读全文