基于限制路径的Dijkstra算法扩展：至多含1条标记边的最短路径求解

核心思路是给每个节点维护两个独立的最短路径状态，区分是否已经使用过标记边，不需要修改Dijkstra的核心堆逻辑，仅扩展状态维度即可，实现简单且效率和原版算法同阶。

步骤说明 #

• 定义两个距离数组：
  • dist0[u]：从源点t到节点u，全程未使用任何标记边的最短路径长度
  • dist1[u]：从源点t到节点u，已经使用过恰好1条标记边的最短路径长度
• 初始化：
  所有距离初始化为无穷大，仅dist0[t] = 0，最小堆初始推入元组(0, t, 0)，第三个参数为标记边使用状态（0代表未使用，1代表已使用）
• 松弛逻辑：
  每次从堆中取出当前距离最小的元组(current_len, u, used_flag)：
  1. 如果used_flag = 0（还没用过标记边）：
     • 遍历u的所有出边(u, v, weight)：
       • 若边不在E'中：判断dist0[v] > current_len + weight，成立则更新dist0[v]，将(dist0[v], v, 0)推入堆
       • 若边在E'中：判断dist1[v] > current_len + weight，成立则更新dist1[v]，将(dist1[v], v, 1)推入堆
  2. 如果used_flag = 1（已经用过1次标记边，不能再用）：
     • 遍历u的所有非标记出边(u, v, weight)：
       • 判断dist1[v] > current_len + weight，成立则更新dist1[v]，将(dist1[v], v, 1)推入堆
• 结果计算：
  对任意节点u，符合要求的最短路径长度为min(dist0[u], dist1[u])，如果两者都是无穷大说明t到u没有符合要求的路径。

复杂度说明 #

总状态数是节点数的2倍，堆操作次数和边数同阶，整体时间复杂度为O(M + NlogN)（N为节点数，M为边数），和原版Dijkstra算法效率一致。

注意：该方案仅适用于边权非负的场景，如果存在负权边可以用相同的双状态逻辑替换为Bellman-Ford或SPFA算法实现。

内容的提问来源于stack exchange，提问作者Rise of Kingdom