带必选加权停靠点的有向图最短路径Dijkstra实现咨询

核心思路 #

问题要求路径必须包含至少一个指定加权停靠点且最终抵达出口，我们可以通过两次Dijkstra算法拆分问题，严格将复杂度控制在O(E log V)范围内，避免枚举所有停靠点的组合。

步骤1：预处理反向图，计算所有节点到最近出口的最短路径 #

• 基于原邻接矩阵构建反向图（所有边的方向反转）
• 将所有出口作为初始节点放入最小堆优先队列，初始距离设为0，其余节点距离设为无穷大
• 对反向图运行Dijkstra算法，得到数组dist_to_exit[]，其中dist_to_exit[u]代表节点u到任意出口的最短路径长度
  • 这一步相当于多源最短路径计算，一次性完成所有节点到最近出口的距离统计，复杂度为O(E log V)

步骤2：从起点出发，计算到所有节点的最短路径 #

• 对原邻接图运行标准Dijkstra算法，以给定起始顶点为起点，得到数组dist_from_start[]，其中dist_from_start[u]代表起点到节点u的最短路径长度
  • 复杂度保持O(E log V)

步骤3：遍历加权停靠点，筛选最优路径 #

• 遍历每个加权停靠点p（包含位置pos和权重w），计算总路径长度：

  total_length = dist_from_start[pos] + w + dist_to_exit[pos]
  

• 跳过dist_from_start[pos]或dist_to_exit[pos]为无穷大的停靠点（这类点无法从起点到达，或无法抵达任何出口）
• 取所有有效total_length中的最小值，对应的路径即为起点→该停靠点→最近出口的最优路径

关键细节说明 #

• 反向图的作用：若直接对每个出口单独跑Dijkstra，复杂度会升至O(K*E log V)（K为出口数量），反向图多源Dijkstra可将复杂度维持在O(E log V)
• 优先队列优化：使用最小堆时，若弹出的节点已被处理过（即当前记录的距离小于堆中存储的距离），直接跳过该条目，避免无效计算

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