带交通信号灯限制的城市1到城市N最短通行时间求解方法问询

可行性说明 #

可以通过扩展标准BFS算法解决该问题，同时Dijkstra最短路径算法也完全适配该场景，两种方案均可实现。

规则梳理 #

首先明确时间计算逻辑：

• 所有信号灯初始为绿色，每T秒切换一次，即周期为2*T：0~T-1为绿灯，T~2T-1为红灯，循环往复
• 抵达非终点城市时若为红灯，需等待到下一次绿灯才能进入城市、出发前往下一个节点
• 抵达终点城市时无需等待信号灯，到达时间即为总耗时
• 每条道路通行耗时固定为C

算法思路 #

方案1：Dijkstra算法（实现简单，通用性强） #

该问题本质是求非负权图的最短路径，所有时间开销均为正数，完全符合Dijkstra算法的适用条件，实现逻辑最直观。

伪代码

// 输入参数：城市总数N，道路邻接表adj，信号灯周期T，单路通行耗时C
// 输出：从城市1到城市N的最短耗时
function minTravelTime(N, adj, T, C):
    // dist[i] 存储到达城市i的最短准入时间（可以出发去下一个节点的时间）
    dist = [infinity] * (N + 1)
    dist[1] = 0
    // 优先队列，存储（准入时间，城市编号），按准入时间升序排列
    priority_queue = [(0, 1)]
    min_end_time = infinity
    
    while priority_queue is not empty:
        current_time, u = heappop(priority_queue)
        // 跳过已找到更优解的节点
        if current_time > dist[u]:
            continue
        // 遍历所有相邻节点
        for v in adj[u]:
            arrival_v = current_time + C
            // 到达终点直接更新最短时间
            if v == N:
                if arrival_v < min_end_time:
                    min_end_time = arrival_v
                continue
            // 计算非终点城市的准入时间
            mod = arrival_v % (2 * T)
            if mod < T:
                access_v = arrival_v
            else:
                access_v = arrival_v + (2 * T - mod)
            // 更新最短准入时间
            if access_v < dist[v]:
                dist[v] = access_v
                heappush(priority_queue, (access_v, v))
    
    return min_end_time

示例验证

代入题目给出的示例参数：N=5，T=3，C=5，邻接表包含边1-2、1-3、2-4、1-4、2-5

• 初始状态：dist[1]=0，优先队列有(0,1)
• 弹出(0,1)，遍历相邻节点：
  • 到2的到达时间是0+5=5，mod 6=5 >=3，准入时间为5+1=6，dist[2]更新为6
  • 到3的到达时间是5，准入时间6，dist[3]=6
  • 到4的到达时间是5，准入时间6，dist[4]=6
• 优先队列弹出最小的(6,2)，遍历相邻节点：
  • 到1的到达时间6+5=11，准入时间12，大于dist[1]=0，跳过
  • 到4的到达时间11，准入时间12，大于dist[4]=6，跳过
  • 到5（终点）的到达时间是6+5=11，min_end_time更新为11
    最终返回结果11，和示例一致。

方案2：扩展BFS（小T场景效率更高） #

当信号灯周期T较小时，可扩展标准BFS的状态为(城市编号, 到达时间模2T的值)，总状态数为N*2T，每个状态仅需处理一次，无需优先队列，时间复杂度更低。

核心逻辑

因为信号灯状态以2T为周期，同一城市如果两次到达的时间模2T的值相同，那么后续等待和通行的时间差完全由到达时间的绝对值决定，仅保留到达时间更小的状态即可。

最终结论 #

两种方案均可以解决该问题，若T取值较大，优先选用Dijkstra算法；若T取值较小，扩展BFS的效率更高。

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