输入两个景点名,计算最短路径,最短路径的长度,C语言代码
时间: 2024-05-09 09:18:23 浏览: 138
对于求解最短路径,我们可以采用 Dijkstra 算法或者 Floyd 算法。下面是采用 Dijkstra 算法的 C 语言代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_V 100 // 最大顶点数
#define INF 0x7fffffff // 无穷大
int graph[MAX_V][MAX_V]; // 邻接矩阵
int distance[MAX_V]; // 起点到各点的最短距离
int visited[MAX_V]; // 是否已经访问
// 求解起点到终点的最短路径及其长度
// 返回最短路径的长度
int dijkstra(int start, int end, int n) {
int i, j, min_dist, next_node;
// 初始化
memcpy(distance, graph[start], sizeof(distance));
memset(visited, 0, sizeof(visited));
visited[start] = 1;
// 循环 n-1 次,每次选出一个顶点加入已访问列表中
for (i = 1; i < n; i++) {
min_dist = INF;
// 选出距离起点最近的未访问顶点 u
for (j = 0; j < n; j++) {
if (!visited[j] && distance[j] < min_dist) {
min_dist = distance[j];
next_node = j;
}
}
// 将 u 加入已访问列表中,并更新起点到其它未访问顶点的距离
visited[next_node] = 1;
for (j = 0; j < n; j++) {
if (!visited[j] && distance[next_node] + graph[next_node][j] < distance[j]) {
distance[j] = distance[next_node] + graph[next_node][j];
}
}
}
// 返回最短路径的长度
return distance[end];
}
int main() {
int n, m, i, start, end, dist;
char name1[30], name2[30];
// 读入景点数和路径数
scanf("%d%d", &n, &m);
// 初始化邻接矩阵
memset(graph, 0x7f, sizeof(graph));
for (i = 0; i < n; i++) {
graph[i][i] = 0;
}
// 读入路径信息
for (i = 0; i < m; i++) {
int u, v, w;
scanf("%s%s%d", name1, name2, &w);
// 将景点名转换成顶点编号
for (u = 0; u < n && strcmp(name1, vertices[u]) != 0; u++);
for (v = 0; v < n && strcmp(name2, vertices[v]) != 0; v++);
// 更新邻接矩阵
graph[u][v] = graph[v][u] = w;
}
// 输入起点和终点的景点名
scanf("%s%s", name1, name2);
// 将景点名转换成顶点编号
for (start = 0; start < n && strcmp(name1, vertices[start]) != 0; start++);
for (end = 0; end < n && strcmp(name2, vertices[end]) != 0; end++);
// 调用 dijkstra 算法求解最短路径,并输出结果
dist = dijkstra(start, end, n);
printf("最短路径长度为:%d\n", dist);
return 0;
}
```
注意,这里假设输入的景点名没有重复,并且顶点编号从 0 开始。如果需要处理重复的景点名,可以考虑使用哈希表等数据结构。
阅读全文
相关推荐
![-](https://img-home.csdnimg.cn/images/20241231044833.png)
![-](https://img-home.csdnimg.cn/images/20241231044955.png)
![-](https://img-home.csdnimg.cn/images/20241231045021.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)