K-最短路径（K Shortest Paths）问题的Yen算法 问题描述 K-最短路径问题要求在有向或无向图中，找出从一个源节点到目标节点的前K条最短路径（按路径长度递增排序）。Yen算法是解决该问题的经典方法，它通过系统地生成候选路径，避免重复计算，适用于非负边权图。 算法步骤详解 1. 初始化 使用Dijkstra算法找出从源节点s到目标节点t的第1条最短路径P₁。 初始化结果列表A = [ P₁ ]，存放已确定的前K短路径。 初始化候选路径集合B（优先队列，按路径长度排序）。 2. 迭代生成第k短路径（k从2到K） 对于上一条路径Pₖ₋₁（即A中第k-1短的路径）： 设置偏离节点索引i从0到L-2（L为Pₖ₋₁的节点数，排除目标节点）。 偏离过程 ： a. 根路径 ：取Pₖ₋₁的前i个节点作为根路径Root = [ s, n₁, n₂, ..., nᵢ ]（i=0时根路径仅含s）。 b. 禁用边 ：对于A中所有已确定路径，若其前i个节点与Root完全一致，则禁用该路径的第i条边（防止重复生成相同路径）。 c. 禁用节点 ：除偏离节点nᵢ外，将Root中其他所有节点从图中临时移除（确保新路径不会提前回到Root）。 d. 计算偏离路径 ：在修改后的图中，用Dijkstra算法从nᵢ到t求最短路径，得到SpurPath。 e. 生成候选路径 ：若SpurPath存在，则完整路径Candidate = Root + SpurPath。将其加入候选集B（需去重）。 从B中选出长度最小的路径作为Pₖ，移入A。若B为空则终止。 3. 关键机制解释 偏离点限制 ：每条新路径仅在偏离点后与之前路径不同，保证多样性。 资源管理 ：禁用边/节点确保路径不重复，但允许部分节点复用。 候选集使用优先队列，保证每次获取全局最优候选。 实例演示（简单图） 图：s→A(1), s→B(2), A→t(3), B→t(1) 求s到t的K=2短路径： 第1短P₁: s→B→t (长度3)。 生成候选： 偏离i=0（根路径[ s ]）： 禁用P₁中s→B边。 计算偏离路径：从s出发，禁用B后得s→A→t (长度4)，候选路径s→A→t。 偏离i=1（根路径[ s,B ]）： 禁用P₁中B→t边，移除节点s。 从B出发无路径到t（t已被移除？修正：根路径中仅移除s，B保留），但B→t边被禁用，故无候选。 候选集中选最短s→A→t作为P₂。 复杂度分析 时间复杂度：O(Kn(m + n log n))，其中n为节点数，m为边数。每次偏离需调用Dijkstra算法。 空间复杂度：O(Kn + m)，存储路径和候选集。 优化方向 使用Eppstein算法可将复杂度降至O(m + n log n + K)，但实现复杂。 候选路径去重时可用哈希校验避免重复计算。