K-最短路径（K-Shortest Paths）算法 K-最短路径算法用于在图中寻找从起点到终点的前K条最短路径，而不仅仅是最短的一条。这在网络路由、物流规划、生物信息学等领域有重要应用，因为实际场景中往往需要考虑多种备选方案。 问题描述 给定一个带权有向图（或无向图）、起点s和终点t，以及整数K>0，找出从s到t的前K条最短路径，按长度递增顺序排列。路径不允许包含重复节点（简单路径），或者在某些变体中允许重复节点但不允许循环。 算法思路 最经典的算法是Yen's算法，它基于最短路径算法（如Dijkstra）进行扩展。核心思想是逐步生成第1, 2, ..., K条路径： 首先找到第1条最短路径 然后通过"偏离"已找到的路径来生成候选路径 从候选路径中选择最短的作为下一条最短路径 详细步骤 步骤1：找到第1条最短路径 使用Dijkstra算法找到从s到t的最短路径，记为P₁。 初始化结果列表A = [ P₁ ] 初始化候选路径集合B = ∅ 步骤2：迭代生成第2到第K条路径 对于k从2到K进行循环： 步骤2.1：分析第k-1条路径 设当前最后找到的路径Pₖ₋₁ = [ s, v₁, v₂, ..., v_ {m-1}, t ]，其中m是路径节点数。 步骤2.2：生成候选路径 对于路径Pₖ₋₁上的每个偏离点vᵢ（i从0到m-2）： 根路径 ：从s到vᵢ的部分路径[ s, v₁, ..., vᵢ ]称为根路径 禁止节点 ：将v₁, v₂, ..., vᵢ标记为禁止节点（在后续搜索中避免使用） 删除边 ：移除边(vᵢ, vᵢ₊₁)，确保新路径与之前路径不同 寻找偏离路径 ：在删除禁止节点和边后的图中，用Dijkstra算法找从vᵢ到t的最短路径 组合路径 ：如果存在这样的路径，将根路径与偏离路径组合得到候选路径 步骤2.3：选择第k条路径 从候选集合B中选择最短的路径作为Pₖ 将Pₖ加入结果列表A，并从B中移除 关键优化技术 1. 剪枝策略 当候选路径长度已超过当前已知的第K条路径时，可提前终止 使用优先队列（最小堆）管理候选路径，按长度排序 2. 高效的最短路径计算 使用双向Dijkstra算法加速搜索 缓存中间结果，避免重复计算 3. 避免重复计算 记录已探索的路径特征，防止生成重复候选 时间复杂度分析 每次迭代需要O(m)次Dijkstra调用（m为路径长度） 总时间复杂度约为O(K·n·(m·E log V))，其中n为平均路径长度 通过优化可降低到O(K·(E + V log V)) 实际应用示例 考虑交通网络规划，寻找从A地到B地的前3条最快路径： 最短路径：A→C→D→B（时间10分钟） 次短路径：A→E→F→B（时间12分钟） 第三短路径：A→C→F→B（时间14分钟） 算法变体 Eppstein算法 ：更高效的实现，时间复杂度O(E + V log V + K) Yen's算法的改进 ：使用更智能的候选路径管理策略 通过这种系统性的偏离和候选生成机制，K-最短路径算法能够有效地找出多条备选路径，为实际决策提供更多灵活性选择。