如何在带双权重及切换条件的图上应用Dijkstra算法求最短路径？

问题核心 #

常规Dijkstra算法仅记录节点的最短距离，无法处理车辆状态（SUV/小型车）和仅能在下划线节点切换车辆的约束，因此会忽略需要回溯节点（如回到A）的更短路径。

解决方案：状态扩展的Dijkstra算法 #

把每个节点的状态从单一节点，扩展为**(当前节点, 当前车辆类型)**，以此区分同一节点下不同车辆状态的最短路径。

1. 状态定义 #

• 每个状态包含两个元素：(node, vehicle)，其中vehicle取值为SUV或小型车
• 初始状态：(A, SUV)，初始距离为0
• 距离存储：用二维数组dist[node][vehicle]记录每个状态的最短距离，初始除dist[A][SUV] = 0外，其余设为无穷大

2. 权重选择规则 #

• 当前为SUV时：
  • 所有边只能使用第一个权重（SUV耗时）
  • 仅当到达下划线节点时，可选择切换为小型车（切换无额外耗时），此时更新dist[当前节点][小型车]为当前总耗时（若更短）
• 当前为小型车时：
  • 每条边可选择第一个权重或第二个权重中更小的那个（无论第二个权重是否更长，都有权选择）
  • 若到达下划线节点，也可选择切回SUV（按需调整）

3. 算法执行步骤 #

1. 使用优先队列（小顶堆）存储待处理状态，元素格式为(总耗时, 当前节点, 当前车辆类型)，初始入队(0, A, SUV)
2. 取出队列中总耗时最小的状态，遍历当前节点的所有邻边：
   • 若当前是SUV：
     • 计算使用第一个权重到达邻节点的总耗时，若该耗时小于dist[邻节点][SUV]，则更新并将(新耗时, 邻节点, SUV)入队
     • 若当前节点是下划线节点，检查dist[当前节点][小型车]是否大于当前总耗时，若是则更新并将(当前总耗时, 当前节点, 小型车)入队
   • 若当前是小型车：
     • 对每条边取min(第一个权重, 第二个权重)作为当前边的耗时，计算到达邻节点的总耗时
     • 若该耗时小于dist[邻节点][小型车]，则更新并将(新耗时, 邻节点, 小型车)入队
3. 重复步骤2，直到队列为空，此时dist[C][SUV]和dist[C][小型车]中的最小值即为A到C的最短耗时

适配正确路径的逻辑说明 #

以给定的正确路径[A,D,E,A,D,C]为例：

• 从初始状态(A, SUV)出发，走A->D（SUV权重）到达D，状态变为(D, SUV)
• 若E是下划线节点，继续走D->E（SUV权重）到达E后，切换为小型车，状态变为(E, 小型车)
• 以(E, 小型车)状态走E->A，使用更优的小型车权重耗时，到达A后状态为(A, 小型车)，这个状态的距离比常规算法仅记录的A的SUV状态更优
• 再从(A, 小型车)出发走A->D（取更优权重），再走D->C（取更优权重），最终得到总耗时270的路径

这种状态扩展的方式，允许同一节点在不同车辆状态下被多次处理，从而捕捉到需要回溯的更短路径。

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