最短偶路径问题到最小权完美匹配问题的归约方法

这个归约的核心是通过状态分层和距离转化，把偶路径的约束转化为匹配问题的结构。我一步步给你讲清楚：

1. 先做状态分层，计算奇偶最短距离 #

首先，我们给原图的每个顶点v赋予两个状态，用来标记到达该顶点时路径的边数奇偶性：

• v₀：到达v时走了偶数条边
• v₁：到达v时走了奇数条边

基于这个状态，我们构造一个分层图G'：

• 顶点集：V' = {v₀ | v ∈ V} ∪ {v₁ | v ∈ V}
• 边集：对于原图中每条边(u, v)（权值w），在G'中添加两条无向边：
  • (u₀, v₁)，权值w：从偶状态的u走这条边到v，状态切换为奇
  • (u₁, v₀)，权值w：从奇状态的u走这条边到v，状态切换为偶

接下来用双状态Dijkstra算法计算两组距离：

• 从s₀出发：
  • dist₀(v)：s₀到v₀的最短距离 → 对应原图中s到v的偶边数最短路径权值
  • dist₁(v)：s₀到v₁的最短距离 → 对应原图中s到v的奇边数最短路径权值
• 从t₀出发（反向计算，即v到t的奇偶路径）：
  • rev_dist₀(v)：t₀到v₀的最短距离 → 原图中v到t的偶边数最短路径权值
  • rev_dist₁(v)：t₀到v₁的最短距离 → 原图中v到t的奇边数最短路径权值

2. 构造最小权完美匹配的输入图 #

现在我们创建一个新图H，用来将偶路径问题转化为完美匹配问题：

• 顶点集：U = V ∪ {x}，其中x是新增的虚拟顶点
• 边权定义：
  1. 任意两个不同的原顶点u, v：
     边(u, v)的权值为 dist₁(u) + w(u, v) + rev_dist₁(v)
     这条边对应原图的偶路径：s→u（奇边数）→v（1条边）→t（奇边数），总边数是奇+1+奇=偶，权值就是三者之和。
  2. 任意原顶点v与虚拟顶点x：
     边(x, v)的权值为 dist₀(v) + rev_dist₀(v)
     这条边对应原图的偶路径：s→v（偶边数）→t（偶边数），总边数是偶+偶=偶，权值是两段偶路径的和。
  3. 虚拟顶点x的自环(x, x)：
     权值为 dist₀(t)，对应原图中直接从s到t的偶边数最短路径。

3. 解的对应关系 #

• 原问题的最短偶路径权值，等于图H中最小权完美匹配的权值。
• 反过来，H的最小权完美匹配对应的边组合，就能还原出原问题的最短偶路径：
  • 如果匹配包含自环(x,x)，说明直接的s→t偶路径是最优解；
  • 如果匹配包含(x,v)，说明最优路径是s→v→t的两段偶路径拼接；
  • 如果匹配包含(u,v)，说明最优路径是s→u→v→t的奇路径+边+奇路径组合。

这个归约的关键在于，我们把所有可能的偶路径都转化为了匹配问题中的边或边组合，而最小权完美匹配会自动选择总权值最小的组合，正好对应原问题的最优解。

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