站点间最少换乘路径问题：代码输出不符预期的原因及修复

问题概述 #

我们需要求解站点间换乘次数最少的路径，输入的每条边代表一条公交线路（连接两个站点），输出要求为最少换乘次数（无路径则输出"No path found"）。

示例输入（4条公交线路）：

4
1 2
2 3
3 4
4 5

从站点1到5的预期输出是3，但现有代码运行后输出4，与预期不符。

问题原因 #

原代码的核心错误是图建模逻辑完全不符合换乘次数的定义：

• 原代码将每个站点作为图的唯一节点，把输入的每条公交线路直接视为站点间的连接，每移动到相邻站点就将换乘次数加1。
• 但实际上，同一公交线路内的站点移动不需要换乘，只有当从一条公交线路切换到另一条时，换乘次数才会增加。示例中从1到5需要乘坐4条独立线路，换乘次数为线路数-1=3，而原代码把站点间的每一步移动都算成一次换乘，因此得到4次错误结果。

修复方案 #

我们需要重新建模图，引入线路节点来区分「同一线路内移动」和「换乘线路」两种操作，具体实现如下：

修复后的代码 #

import heapq

def min_transfers(edges, start, end):
    if start == end:
        return 0
    
    # 构建站点与线路的双向映射
    station_to_lines = {}
    line_to_stations = {}
    for line_idx, (u, v) in enumerate(edges):
        line_id = f"line_{line_idx}"
        # 记录线路对应的站点
        line_to_stations[line_id] = [u, v]
        # 记录站点关联的线路
        station_to_lines.setdefault(u, []).append(line_id)
        station_to_lines.setdefault(v, []).append(line_id)
    
    # 存储站点的最小换乘次数
    station_dist = {start: 0}
    # 存储线路的最小换乘次数（即乘坐该线路所需的换乘次数）
    line_dist = {}
    
    # 优先队列：(当前换乘次数, 节点类型, 节点ID)
    pq = []
    # 初始化：从起点出发，所有经过起点的线路无需换乘（换乘次数0）
    for line in station_to_lines.get(start, []):
        line_dist[line] = 0
        heapq.heappush(pq, (0, 'line', line))
    
    while pq:
        current_dist, node_type, node = heapq.heappop(pq)
        
        # 处理线路节点：遍历该线路覆盖的所有站点
        if node_type == 'line':
            # 如果当前记录的线路换乘次数更小，跳过重复处理
            if line_dist.get(node, float('inf')) < current_dist:
                continue
            # 遍历线路上的站点
            for station in line_to_stations[node]:
                # 更新站点的最小换乘次数
                if station not in station_dist or current_dist < station_dist[station]:
                    station_dist[station] = current_dist
                    # 到达终点直接返回
                    if station == end:
                        return current_dist
                    # 从当前站点换乘其他线路，换乘次数+1
                    for next_line in station_to_lines.get(station, []):
                        if next_line == node:
                            continue  # 跳过同一条线路，避免无效循环
                        new_dist = current_dist + 1
                        if next_line not in line_dist or new_dist < line_dist[next_line]:
                            line_dist[next_line] = new_dist
                            heapq.heappush(pq, (new_dist, 'line', next_line))
    
    # 终点不可达
    return "No path found"

# 示例测试
edges = [
    (1, 2),
    (2, 3),
    (3, 4),
    (4, 5)
]
start = 1
end = 5

print(min_transfers(edges, start, end))  # 输出：3

修复逻辑说明 #

1. 双向映射构建：创建站点到线路、线路到站点的映射，明确每条线路覆盖的站点，以及每个站点可换乘的线路。
2. 双类型节点状态：用station_dist记录到达每个站点的最小换乘次数，用line_dist记录乘坐每条线路所需的换乘次数。
3. 优先队列遍历：
   • 初始时，从起点站点出发的所有线路无需换乘（次数为0），加入队列。
   • 处理线路节点时，更新其覆盖站点的换乘次数；从站点出发换乘其他线路时，换乘次数加1，加入队列。
   • 一旦到达终点站点，立即返回当前换乘次数（优先队列保证第一次到达即为最小次数）。

额外测试场景 #

如果输入包含直接连接1和5的线路：

edges = [
    (1, 2),
    (2, 3),
    (3, 4),
    (4, 5),
    (1, 5)
]

调用函数后会输出0，符合预期（直接乘坐1-5线路，无需换乘）。

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