调整Dijkstra算法用于公交路径规划——最小化换乘次数

看起来你已经把公交系统的图模型搭得很扎实了——用站点当顶点、耗时当边权，还结合了时间约束做了Dijkstra的变体，这点很贴合公交系统的实际场景！要实现换乘次数最小化，核心是给算法加上「换乘次数优先」的优先级逻辑，下面是具体的调整思路和实现细节：

1. 扩展状态节点的信息维度 #

传统Dijkstra只追踪「到达站点的最小耗时」，但要兼顾换乘次数，我们需要把换乘次数和「上一班公交ID」加入状态维度：

• 每个队列元素存储 (换乘次数, 到达时间, 当前站点, 上一班公交ID)
• 同时维护一个best字典，记录每个(站点, 换乘次数)组合对应的最小到达时间，避免重复处理更差的状态（比如换乘次数更多、到达时间还更晚的路径）

2. 重构优先级队列的排序规则 #

原来的队列按「到达时间」升序排序，现在要改成先按换乘次数升序，再按到达时间升序。这样算法会优先探索换乘次数更少的路径，只有当换乘次数相同时，才选择耗时更短的——这是实现换乘次数最小化的核心，让优先级队列的资源向「少换乘」路径倾斜。

3. 修改松弛（Relaxation）逻辑 #

处理每条边时，要判断是否发生换乘：

• 如果当前乘坐的公交和上一段路径的公交是同一条（通过bus_id判断），换乘次数保持不变；
• 如果切换了公交，换乘次数加1。

然后判断新状态是否值得加入队列：

• 若目标站点的(站点, 新换乘次数)组合没有记录，或者新的到达时间比已记录的同换乘次数下的时间更短，就将新状态推入队列；
• 即使新到达时间稍晚，但换乘次数比当前记录的最小换乘次数更小，也必须加入队列（因为换乘次数优先）。

4. 适配多段公交往返同站点的场景 #

你已经做了「筛选出发时间晚于当前行程时间的边」的逻辑，这点要保留。同时注意：同一公交的往返路段（比如公交A从S1到S2，再从S2回S1）不算换乘，只有切换不同bus_id的公交时才增加换乘次数。

伪代码示例 #

from heapq import heappush, heappop

def dijkstra_min_transfer(start_stop, end_stop, bus_graph):
    # 初始化优先级队列：(换乘次数, 到达时间, 当前站点, 上一班公交ID)
    priority_queue = []
    heappush(priority_queue, (0, 0, start_stop, None))
    
    # 记录最优状态：key=(站点, 换乘次数), value=最小到达时间
    best_states = {}
    
    min_transfer_count = float('inf')
    # 若需要记录具体路径，可额外维护路径追踪字典
    
    while priority_queue:
        current_transfers, current_time, current_stop, last_bus = heappop(priority_queue)
        
        # 若当前状态的换乘次数已超过已知最小值，直接跳过
        if current_transfers > min_transfer_count:
            continue
        
        # 到达终点，更新最小换乘次数
        if current_stop == end_stop:
            if current_transfers < min_transfer_count:
                min_transfer_count = current_transfers
            continue
        
        # 遍历当前站点所有符合时间要求的出站边
        for edge in bus_graph[current_stop]:
            bus_id, next_stop, depart_time, travel_time = edge
            # 跳过出发时间早于当前到达时间的班次
            if depart_time < current_time:
                continue
            
            new_arrival_time = depart_time + travel_time
            new_transfers = current_transfers
            # 切换公交则换乘次数+1
            if bus_id != last_bus:
                new_transfers += 1
            
            # 检查是否需要加入队列
            state_key = (next_stop, new_transfers)
            if state_key not in best_states or new_arrival_time < best_states[state_key]:
                best_states[state_key] = new_arrival_time
                heappush(priority_queue, (new_transfers, new_arrival_time, next_stop, bus_id))
    
    return min_transfer_count

关键注意事项 #

• 必须给每条公交路线分配唯一的bus_id，这是判断是否换乘的核心依据；
• 如果你的图结构还没关联bus_id，需要先扩展边的信息，把每条边和对应的公交路线绑定；
• 终止条件要等到所有换乘次数小于当前最小值的状态都处理完毕，不能像传统Dijkstra那样第一次到达终点就返回，因为可能存在换乘次数更少但到达时间稍晚的路径。

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