设计一个长沙地铁线路查询系统，为长沙地铁乘客咨询从任一个站点到另一个站点之间的最短路径问题。用算法表示

这个问题可以用Dijkstra算法来解决。以下是算法步骤：

1. 初始化：将起点的距离设为0，将所有其他站点的距离设为无穷大。

2. 选择一个当前距离最短的站点，将其标记为已访问。

3. 对于当前站点的所有邻居，如果通过当前站点到达其邻居的距离比当前记录的距离更短，则更新邻居的距离。

4. 重复步骤2和3，直到所有站点都被标记为已访问或者没有可达站点。

5. 最终记录下每个站点到起点的最短距离，该记录即为最短路径。

在实现过程中，可以使用优先队列来存储当前距离最短的站点，以便快速地检索到下一个站点。同时，可以使用邻接列表来存储每个站点的邻居和距离，以快速地遍历所有邻居。

相关问题

设计一个长沙地铁线路查询系统，为长沙地铁乘客咨询从任一个站点到另一个站点之间的最短路径问题。并生成代码

以下是一个使用 Python 实现的长沙地铁线路查询系统的示例代码。该代码使用了 Dijkstra 算法来计算最短路径。

import heapq

# 定义地铁站点和线路
stations = [
    '岳麓区政府',
    '岳麓大道',
    '望月湖',
    '湖南大学',
    '枫林路',
    '银盆岭',
    '梅溪湖'
]

lines = {
    '1号线': ['岳麓区政府', '岳麓大道', '望月湖', '湖南大学', '枫林路', '银盆岭', '梅溪湖']
}

# 定义邻接列表
subway = {
    '岳麓区政府': {'岳麓大道': 0.5},
    '岳麓大道': {'岳麓区政府': 0.5, '望月湖': 0.8},
    '望月湖': {'岳麓大道': 0.8, '湖南大学': 0.6},
    '湖南大学': {'望月湖': 0.6, '枫林路': 1.0},
    '枫林路': {'湖南大学': 1.0, '银盆岭': 1.2},
    '银盆岭': {'枫林路': 1.2, '梅溪湖': 1.5},
    '梅溪湖': {'银盆岭': 1.5}
}

def dijkstra(graph, start, end):
    # 初始化距离和父节点
    distances = {start: 0}
    parents = {start: None}
    # 初始化优先队列
    queue = [(0, start)]
    while queue:
        # 取出当前距离最短的站点
        current_distance, current_node = heapq.heappop(queue)
        # 如果当前站点已经是终点，则返回最短路径
        if current_node == end:
            path = []
            while current_node:
                path.append(current_node)
                current_node = parents[current_node]
            path.reverse()
            return path, distances[end]
        # 遍历当前站点的邻居
        for neighbor, distance in graph[current_node].items():
            # 计算通过当前站点到达邻居的距离
            new_distance = current_distance + distance
            # 如果比之前记录的距离更短，则更新距离和父节点
            if neighbor not in distances or new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                parents[neighbor] = current_node
                heapq.heappush(queue, (new_distance, neighbor))
    # 如果无法到达终点，则返回空路径和无穷大的距离
    return [], float('inf')

# 定义查询函数
def query(start, end):
    if start not in stations or end not in stations:
        print('输入站点不存在，请重新输入。')
        return
    path, distance = dijkstra(subway, start, end)
    if not path:
        print('无法到达目的地，请重新输入。')
        return
    print(f'从{start}到{end}的最短路径是：')
    for i in range(len(path) - 1):
        line = None
        for l, s in lines.items():
            if path[i] in s and path[i + 1] in s:
                line = l
                break
        print(f'{i + 1}. {path[i]}（{line}） ->')
    print(f'{len(path)}. {path[-1]}')

# 示例：从岳麓区政府到梅溪湖的最短路径
query('岳麓区政府', '梅溪湖')

在以上代码中，我们首先定义了长沙地铁的站点和线路。然后，我们将地铁线路建立为邻接列表 `subway`，其中每个站点对应一个字典，字典的键是邻居站点名，值是到邻居站点的距离。接着，我们实现了 `dijkstra` 函数来计算最短路径，该函数的输入参数为邻接列表、起点和终点，输出结果为最短路径和距离。在该函数中，我们使用了一个 `distances` 字典来记录每个站点到起点的距离，使用一个 `parents` 字典来记录每个站点的父节点，使用一个优先队列 `queue` 来存储当前距离最短的站点。在每次循环中，我们从优先队列中取出当前距离最短的站点，然后遍历其邻居，更新邻居的距离和父节点。如果当前站点已经是终点，则返回最短路径。如果无法到达终点，则返回空路径和无穷大的距离。

最后，我们定义了 `query` 函数来实现查询功能。该函数首先检查输入的起点和终点是否存在，如果不存在则提示用户重新输入。然后，调用 `dijkstra` 函数来计算最短路径，并将最短路径按照站点顺序输出。在输出时，我们还根据站点所在的线路来显示线路信息。

长沙地铁线路查询并加上查询最短路径的C语言代码

以下是使用Dijkstra算法实现长沙地铁线路最短路径查询的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 1e9 // 定义无穷大

// 定义地铁站结构体
typedef struct {
    char name[20]; // 站名
    int id; // 站点编号
    int line; // 所属线路
} Station;

// 定义邻接表节点结构体
typedef struct {
    int to; // 指向的站点编号
    int weight; // 边权值，即两站之间的距离
    int next; // 下一个邻接表节点的编号
} Edge;

// 定义邻接表结构体
typedef struct {
    int head[100]; // 邻接表头指针数组
    Edge edge[1000]; // 邻接表节点数组
    int cnt; // 邻接表节点计数器
} AdjacencyList;

// 定义全局变量
Station station[100]; // 站点数组
AdjacencyList graph; // 地铁线路邻接表
int stationCnt = 0; // 站点计数器

// 初始化邻接表
void initGraph() {
    memset(graph.head, -1, sizeof(graph.head)); // 初始化邻接表头指针数组
    graph.cnt = 0; // 初始化邻接表节点计数器
}

// 添加站点
void addStation(char *name, int line) {
    strcpy(station[stationCnt].name, name);
    station[stationCnt].id = stationCnt;
    station[stationCnt].line = line;
    stationCnt++;
}

// 添加边
void addEdge(int u, int v, int w) {
    graph.edge[graph.cnt].to = v;
    graph.edge[graph.cnt].weight = w;
    graph.edge[graph.cnt].next = graph.head[u];
    graph.head[u] = graph.cnt++;
}

// 查询站点编号
int findStation(char *name) {
    for (int i = 0; i < stationCnt; i++) {
        if (strcmp(station[i].name, name) == 0) {
            return i;
        }
    }
    return -1; // 没有找到该站点
}

// 查询最短路径
void dijkstra(int start, int end) {
    int dis[100]; // 存储起点到各站点的最短距离
    int vis[100]; // 标记站点是否已访问
    int pre[100]; // 记录每个站点的前驱站点
    memset(dis, INF, sizeof(dis)); // 初始化距离数组
    memset(vis, 0, sizeof(vis)); // 初始化访问标记数组
    memset(pre, -1, sizeof(pre)); // 初始化前驱数组
    dis[start] = 0; // 起点到起点的最短距离为0

    // Dijkstra算法
    for (int i = 0; i < stationCnt; i++) {
        int minDis = INF, u = -1;
        for (int j = 0; j < stationCnt; j++) {
            if (!vis[j] && dis[j] < minDis) {
                minDis = dis[j];
                u = j;
            }
        }
        if (u == -1) break;
        vis[u] = 1;
        for (int j = graph.head[u]; j != -1; j = graph.edge[j].next) {
            int v = graph.edge[j].to;
            int w = graph.edge[j].weight;
            if (!vis[v] && dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                pre[v] = u;
            }
        }
    }

    // 输出最短路径
    printf("从 %s 到 %s 的最短路径为：\n", station[start].name, station[end].name);
    printf("%s", station[start].name);
    int path[100], cnt = 0;
    for (int i = end; i != -1; i = pre[i]) {
        path[cnt++] = i;
    }
    for (int i = cnt - 2; i >= 0; i--) {
        printf(" -> %s", station[path[i]].name);
    }
    printf("\n最短距离为：%d\n", dis[end]);
}

int main() {
    // 添加地铁站点
    addStation("岳麓山", 1);
    addStation("梅溪湖", 1);
    addStation("南瓜", 1);
    addStation("高云", 1);
    addStation("岳麓大道", 1);
    addStation("轨道交通大厦", 1);
    addStation("西湖公园", 2);
    addStation("芙蓉广场", 2);
    addStation("五一广场", 2);
    addStation("万家丽", 2);
    addStation("长沙火车站", 2);
    addStation("开福寺", 2);

    // 添加地铁线路
    initGraph();
    addEdge(0, 1, 3);
    addEdge(1, 2, 2);
    addEdge(2, 3, 2);
    addEdge(3, 4, 2);
    addEdge(4, 5, 2);
    addEdge(5, 6, 2);
    addEdge(6, 7, 2);
    addEdge(7, 8, 2);
    addEdge(8, 9, 2);
    addEdge(9, 10, 2);
    addEdge(10, 11, 2);
    addEdge(11, 7, 1);
    addEdge(8, 5, 1);
    addEdge(4, 9, 1);

    // 查询最短路径
    int start = findStation("岳麓山");
    int end = findStation("长沙火车站");
    dijkstra(start, end);

    return 0;
}

其中，`addStation`函数用于添加地铁站点，`addEdge`函数用于添加地铁线路，`findStation`函数用于查询站点编号，`dijkstra`函数用于查询最短路径。在本示例中，我们以长沙地铁1号线和2号线为例添加地铁站点和地铁线路，并查询了岳麓山站到长沙火车站的最短路径。