请改进该程序,使能输出给定的两点之间的最近距离,并输出路径。
时间: 2024-02-13 13:00:38 浏览: 21
为了实现您的需求,我们需要使用图论中的最短路算法。这里我推荐使用Dijkstra算法,它可以求解给定起点到其他所有点的最短路径,同时也可以记录下每个点的前驱节点,从而输出路径。下面是改进后的代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_N 1000
int graph[MAX_N][MAX_N];
int dist[MAX_N];
int visited[MAX_N];
int pre[MAX_N];
void dijkstra(int n, int start) {
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
pre[i] = -1;
}
dist[start] = 0;
for (int i = 0; i < n; i++) {
int minDist = INT_MAX, u = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
if (u == -1) break;
visited[u] = 1;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != -1 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
pre[v] = u;
}
}
}
}
void printPath(int start, int end) {
if (pre[end] == -1) {
printf("%d", end);
return;
}
int path[MAX_N], count = 0;
int curr = end;
while (curr != -1) {
path[count++] = curr;
curr = pre[curr];
}
for (int i = count - 1; i >= 0; i--) {
printf("%d", path[i]);
if (i != 0) printf("->");
}
}
int main() {
int n, m;
printf("请输入节点数和边数:");
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = -1;
}
}
printf("请输入边和权值:\n");
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
graph[u][v] = w;
graph[v][u] = w; // 如果是无向图需要加上这一句
}
printf("请输入起点和终点:");
int start, end;
scanf("%d %d", &start, &end);
dijkstra(n, start);
printf("起点%d到终点%d的最短距离为:%d\n", start, end, dist[end]);
printf("路径为:");
printPath(start, end);
printf("\n");
return 0;
}
```
这段代码中,我们使用了邻接矩阵来表示图,-1表示两个点之间没有边相连。在主函数中,我们先输入节点数和边数,然后输入每条边的起点、终点和权值。接着输入起点和终点,调用dijkstra函数求解最短路径和前驱节点,最后调用printPath函数输出路径。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)