求支持重复顶点的O(ElogV)最短路径算法及拼车路径解法

你的问题核心是节点存在两种状态（携带乘客/未携带乘客），直接用原节点的Dijkstra会忽略状态差异，导致无法处理绕路搭乘客的最优路径。通过状态拆分，我们可以把问题转化为无负权的状态图，复用Dijkstra的O(ElogV)时间复杂度优势，同时允许原节点被多次访问（对应不同状态）。

具体实现步骤 #

1. 状态建模 #

将原图中的每个节点u拆分为两个状态节点：

• u₀：处于节点u，未携带乘客
• u₁：处于节点u，已携带乘客
  整个状态图的总顶点数为2V，满足复杂度控制要求。

2. 构建状态图的边 #

根据道路规则添加以下几类边（所有边的权重均为非负耗时）：

• 普通道路：无论是否携带乘客都可通行，添加两条边：
  • 从u₀到v₀，权重为u到v的普通道路耗时
  • 从u₁到v₁，权重为u到v的普通道路耗时
• 拼车道路：仅携带乘客时可通行，添加边：
  • 从u₁到v₁，权重为u到v的拼车道路耗时（题目明确此耗时≤普通道路）
• 乘客搭载操作：在指定的乘客节点p，未携带乘客时可转为已携带状态，添加边：
  • 从p₀到p₁，权重为0（仅状态转换，无移动耗时）

3. 运行Dijkstra算法 #

• 起点设为A₀（从节点A出发，未携带乘客）
• 终点取到达B₀的最短路径和到达B₁的最短路径中的较小值（到达节点B时，无论是否携带乘客均视为完成行程）

为什么这个方法可行？ #

• 状态拆分后，原节点的重复访问对应不同的状态节点（比如u₀和u₁是两个独立的顶点），完全符合Dijkstra的运行逻辑，不会被“贪心跳过已访问节点”的规则限制
• 所有边的权重都是非负的（耗时为正，状态转换边权重为0），满足Dijkstra的适用条件，时间复杂度为O((2E)log(2V))，等价于O(ElogV)
• 自然支持“绕路搭乘客再返回原路线”的最优路径选择，因为状态图会自动计算这类路径的总耗时

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