地铁线路最短路径Dijkstra算法

地铁线路最短路径问题可以使用Dijkstra算法来解决。具体步骤如下：

1. 创建一个包含所有地铁站点的节点集合，并将起点设置为距离起点最近的节点。
2. 对于每个节点，计算从起点到该节点的距离，并将该距离保存在节点中。
3. 对于每个节点，计算从起点到该节点的最短路径，并将该路径保存在节点中。
4. 标记当前节点为已访问。
5. 对于当前节点的每个邻居节点，计算从起点到该邻居节点的距离，并将该距离保存在邻居节点中。
6. 如果从起点到该邻居节点的距离小于该邻居节点中保存的距离，则更新该邻居节点的距离和最短路径。
7. 从未访问的节点中选择距离起点最近的节点作为下一个当前节点，并重复步骤4-6，直到所有节点都被访问过。

下面是一个使用Dijkstra算法求解地铁线路最短路径的Python代码示例：

import heapq

def dijkstra(graph, start, end):
    # 初始化距离和路径
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    path = {}

    # 创建一个优先队列，并将起点加入队列
    pq = [(0, start)]

    while pq:
        # 取出距离起点最近的节点
        (dist, current_node) = heapq.heappop(pq)

        # 如果当前节点已经访问过，则跳过
        if dist > distances[current_node]:
            continue

        # 遍历当前节点的邻居节点
        for neighbor, weight in graph[current_node].items():
            # 计算从起点到邻居节点的距离
            distance = dist + weight

            # 如果从起点到邻居节点的距离小于邻居节点中保存的距离，则更新邻居节点的距离和路径
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                path[neighbor] = current_node

                # 将邻居节点加入优先队列
                heapq.heappush(pq, (distance, neighbor))

        # 如果已经找到终点，则返回最短路径和距离
        if current_node == end:
            path_list = []
            while current_node in path:
                path_list.append(current_node)
                current_node = path[current_node]
            path_list.append(start)
            path_list.reverse()
            return path_list, distances[end]

    # 如果无法到达终点，则返回空路径和无穷大的距离
    return [], float('inf')