设计一个长沙地铁线路查询系统,为长沙地铁乘客咨询从任一个站点到另一个站点之间的最短路径问题。并提供完整的可运行的C语言代码
时间: 2024-03-21 15:41:31 浏览: 14
好的,这是一个比较复杂的问题,需要用到图论算法中的最短路径算法。我会给你提供一个基于 Dijkstra 算法的 C 语言实现,具体实现过程如下:
1. 定义图的结构体(包括站点名称、站点间的里程、站点数量等);
2. 定义 Dijkstra 算法的核心数据结构(包括起点、终点、最短路径数组等);
3. 读入地铁站点信息,建立图;
4. 实现 Dijkstra 算法,求出最短路径;
5. 输出最短路径信息。
下面是完整的可运行的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX_STATION 100 // 最大站点数量
#define INF INT_MAX // 定义正无穷
// 定义图的结构体
typedef struct {
char name[50]; // 站点名称
int distance[MAX_STATION]; // 站点间的里程
} Station;
// 定义 Dijkstra 算法的核心数据结构
typedef struct {
int start; // 起点
int end; // 终点
int shortest_path[MAX_STATION]; // 最短路径数组
int visited[MAX_STATION]; // 是否已访问数组
} Dijkstra;
Station subway_map[MAX_STATION]; // 存储地铁图
int num_stations = 0; // 站点数量
// 添加站点
void add_station(char *name, int *distance) {
strcpy(subway_map[num_stations].name, name);
memcpy(subway_map[num_stations].distance, distance, sizeof(int) * num_stations);
num_stations++;
}
// 查找站点在地铁图中的索引
int find_station(char *name) {
for (int i = 0; i < num_stations; i++) {
if (strcmp(subway_map[i].name, name) == 0) {
return i;
}
}
return -1;
}
// Dijkstra 算法求最短路径
void dijkstra(Dijkstra *dij) {
// 初始化
for (int i = 0; i < num_stations; i++) {
dij->shortest_path[i] = subway_map[dij->start].distance[i];
dij->visited[i] = 0;
}
dij->shortest_path[dij->start] = 0;
// 访问起点
dij->visited[dij->start] = 1;
// 进行 n-1 次循环
for (int i = 0; i < num_stations - 1; i++) {
int min_distance = INF;
int current_station_index = -1;
// 找到距离起点最近的站点
for (int j = 0; j < num_stations; j++) {
if (!dij->visited[j] && dij->shortest_path[j] < min_distance) {
current_station_index = j;
min_distance = dij->shortest_path[j];
}
}
// 标记当前站点为已访问
dij->visited[current_station_index] = 1;
// 更新最短路径数组
for (int j = 0; j < num_stations; j++) {
int distance = subway_map[current_station_index].distance[j];
if (!dij->visited[j] && dij->shortest_path[current_station_index] + distance < dij->shortest_path[j]) {
dij->shortest_path[j] = dij->shortest_path[current_station_index] + distance;
}
}
}
}
int main() {
int n, m;
char start[50], end[50];
// 读入站点数量和站点信息
scanf("%d", &n);
for (int i = 0; i < n; i++) {
char name[50];
int distance[MAX_STATION];
scanf("%s", name);
for (int j = 0; j < i; j++) {
scanf("%d", &distance[j]);
}
add_station(name, distance);
}
// 读入咨询次数
scanf("%d", &m);
// 处理每个咨询
for (int i = 0; i < m; i++) {
scanf("%s %s", start, end);
// 查找起点和终点在地铁图中的索引
int start_index = find_station(start);
int end_index = find_station(end);
// 如果没有找到,输出错误信息
if (start_index == -1 || end_index == -1) {
printf("Invalid query!\n");
continue;
}
// 进行 Dijkstra 算法
Dijkstra dij = {start_index, end_index};
dijkstra(&dij);
// 输出最短路径
if (dij.shortest_path[end_index] != INF) {
printf("%d\n", dij.shortest_path[end_index]);
} else {
printf("No path exists!\n");
}
}
return 0;
}
```
以上就是一个基于 Dijkstra 算法实现的长沙地铁线路查询系统的 C 语言代码。