K-最短路径（K Shortest Paths）问题

问题描述
K-最短路径问题要求在一个带权有向图中，找出从源节点到目标节点的前K条最短路径（按路径长度递增排序）。这些路径必须是简单路径（无重复节点），且允许路径长度相同。该问题在路由规划、网络分析等领域有广泛应用。

关键思路
直接扩展Dijkstra算法无法解决此问题，因为Dijkstra仅能找出一条最短路径。K-最短路径的经典解法是Yen's算法，其核心思想是通过"偏离路径"逐步生成候选路径。

步骤1：基础概念与术语

• 最短路径：从源节点s到目标节点t的路径中，权重之和最小的路径。
• 候选路径列表：存储当前找到的潜在路径，按长度排序。
• 结果路径列表：保存最终确定的K条最短路径。
• 偏离节点：在已有路径基础上，通过改变其中某个节点延伸出的新路径。

步骤2：Yen's算法流程

1. 初始化：

   • 使用Dijkstra算法找出第1条最短路径P₁，加入结果列表。
   • 初始化候选路径列表为空。

2. 迭代生成第k短路径（k从2到K）：

   • 对于上一条路径Pₖ₋₁的每个节点（除目标节点外），作为偏离点生成新候选路径。
   • 具体生成方法：
     a. 根路径：从源节点s到偏离节点A的前缀路径（与Pₖ₋₁相同）。
     b. 偏离边：选择一条从A出发、不在Pₖ₋₁中的边（避免重复）。
     c. 后缀路径：从偏离边的另一端到目标节点t的最短路径，且不经过根路径中已使用的节点（避免环路）。
   • 将生成的新路径加入候选列表。

3. 选择当前最短候选路径：

   • 从候选列表中选出权重最小的路径作为Pₖ，移入结果列表。
   • 重复步骤2直到找到K条路径或候选列表为空。

步骤3：实例演示（简单图例）
考虑下图（s为源点，t为目标点）：

s --2→ A --3→ t
s --1→ B --4→ t
s --5→ t

• 第1短路径P₁：s→B→t（长度1+4=5）。
• 生成第2短路径：
  • 偏离点s：根路径为空，从s出发的未用边有(s,A)和(s,t)。
    • 对于(s,A)：后缀路径需从A到t不经过已用节点（无限制），最短路径A→t（长度3），生成路径s→A→t（总长5）。
    • 对于(s,t)：路径s→t（长度5）。
  • 偏离点B：根路径s→B，从B出发的未用边无（仅B→t已用），跳过。
  • 候选列表：{s→A→t:5, s→t:5}。选择任一（如s→A→t）作为P₂。

步骤4：关键细节与优化

• 避免环路：计算后缀路径时，临时移除根路径中的节点（除偏离点），确保简单路径。
• 高效最短路径计算：每次调用Dijkstra时可复用之前计算的中间结果（如使用剪枝技巧）。
• 去重：候选路径可能重复，需用数据结构（如哈希集合）过滤。

步骤5：复杂度分析

• 时间复杂度：O(K·n·(m + n log n))，其中n为节点数，m为边数。每生成一条路径需O(n)次Dijkstra调用。
• 空间复杂度：O(K·n + m)，存储路径和图结构。

总结
Yen's算法通过系统性地偏离已有路径，逐步生成候选路径，平衡了完备性与效率。实际应用中常结合A*算法加速后缀路径计算，并采用堆结构维护候选列表。