多重叠线路地铁网络最短路径Python算法实现咨询

1. 地铁网络建模（数据结构设计） #

首先将地铁系统抽象为加权无向图：

• 节点：地铁站点（换乘站统一用同一个名称，确保节点唯一性）
• 边：相邻站点的连接，权重为运行时间，同时记录所属线路（用于处理换乘逻辑）

用字典存储邻接表，示例结构如下：

# 键：站点名称；值：邻接站点列表，每个元素为(目标站点, 运行时间, 所属线路)
subway_graph = {
    "国王十字": [("尤斯顿", 2, "北线"), ("圣潘克拉斯", 1, "维多利亚线")],
    "尤斯顿": [("国王十字", 2, "北线"), ("沃伦街", 3, "北线")],
    "沃伦街": [("尤斯顿", 3, "北线"), ("牛津 Circus", 2, "维多利亚线")],
    "圣潘克拉斯": [("国王十字", 1, "维多利亚线"), ("罗素广场", 2, "维多利亚线")],
    "罗素广场": [("圣潘克拉斯", 2, "维多利亚线"), ("牛津 Circus", 3, "维多利亚线")],
    "牛津 Circus": [("沃伦街", 2, "北线"), ("罗素广场", 3, "维多利亚线")]
}

2. Dijkstra算法核心实现 #

利用Python内置的heapq模块实现最小堆，维护两个核心字典：

• shortest_distances：记录从起点到各站点的最短耗时
• predecessors：记录各站点的前驱节点及所属线路，用于后续还原路径

import heapq

def dijkstra(subway_graph, start, end):
    # 初始化：所有站点默认最短耗时为无穷大，起点耗时为0
    shortest_distances = {station: float('inf') for station in subway_graph}
    shortest_distances[start] = 0
    # 初始化前驱节点字典
    predecessors = {station: None for station in subway_graph}
    # 优先队列：(当前总耗时, 当前站点, 当前线路)
    heap = []
    heapq.heappush(heap, (0, start, None))

    while heap:
        current_time, current_station, current_line = heapq.heappop(heap)

        # 到达终点则提前终止
        if current_station == end:
            break
        # 当前路径耗时已超过已知最短，直接跳过
        if current_time > shortest_distances[current_station]:
            continue

        # 遍历所有邻接站点
        for neighbor, segment_time, line in subway_graph[current_station]:
            # 计算新路径总耗时，如需添加换乘耗时可在此处修改
            new_time = current_time + segment_time
            # 可选：跨线路换乘时增加固定耗时（比如2分钟步行时间）
            # if current_line is not None and current_line != line:
            #     new_time += 2

            # 发现更短路径则更新
            if new_time < shortest_distances[neighbor]:
                shortest_distances[neighbor] = new_time
                predecessors[neighbor] = (current_station, line)
                heapq.heappush(heap, (new_time, neighbor, line))

    return shortest_distances[end], predecessors

3. 路径还原 #

通过前驱字典从终点回溯到起点，反转后得到完整行程路径：

def reconstruct_path(predecessors, start, end):
    path = []
    current = end
    while current is not None:
        prev_info = predecessors[current]
        if prev_info:
            prev_station, line = prev_info
            path.append((prev_station, current, line))
        current = prev_info[0] if prev_info else None
    # 反转路径得到起点到终点的顺序
    path.reverse()
    return path

4. 完整使用示例 #

# 定义起点和终点
start_station = "国王十字"
end_station = "牛津 Circus"

# 计算最短耗时和前驱信息
shortest_time, predecessors = dijkstra(subway_graph, start_station, end_station)
# 还原路径
trip_path = reconstruct_path(predecessors, start_station, end_station)

# 输出结果
print(f"从{start_station}到{end_station}的最短耗时：{shortest_time}分钟")
print("行程详情：")
for segment in trip_path:
    print(f"乘坐{segment[2]}线：{segment[0]} → {segment[1]}")

关键注意事项 #

• 换乘逻辑：如果需要考虑换乘的额外时间，可在计算new_time时添加固定值（比如跨线路时加2分钟）
• 站点校验：实际使用时需添加起点/终点是否在图中的校验逻辑，避免KeyError
• 堆的特性：heapq是最小堆，每次弹出的都是当前耗时最短的节点，完全符合Dijkstra算法的贪心逻辑

内容的提问来源于stack exchange，提问作者clueless2334