C++ Yen 的 K-最短路径算法

在 C++ 中，Yen 的 K 最短路径算法 用于在加权图中找到源点和目标点之间的 K 条最短唯一路径。Yen 的方法通过从先前确定的路径中产生偏差，迭代地寻找最短路径（由 Dijkstra 算法发现）。每个路径偏差都存储在一个优先队列中，以快速识别下一个可能的 shortest path。当存在多条路径时，该方法可用于网络路由和物流等场景。Yen 的方法在 C++ 中实现，使用适当的数据结构，如优先队列和向量，以有效地管理路径及其偏差。

关键概念

• Yen 开发的技术基于 Dijkstra 算法，该算法用于在加权图中查找节点之间的最短路径。
• 在找到最短路径后，Yen 的算法通过引入偏差，迭代地寻找其他路径，从而避免循环或以前发现的路径。
• K 条路径： Yen 的方法并不仅仅停留在最初的最短路径；相反，它会搜索直到找到总共 K 条不同的最短路径。

C++ 实现步骤

在 C++ 中实现 Yen 的 K 最短路径算法时，可以使用常用库（如标准模板库 (STL)）作为数据结构，例如向量（用于存储路径）和优先队列（用于高效路径查找）。对于最短路径发现，基本 Dijkstra 算法 可以作为优先队列来实现。

• 使用最短路径算法，例如 Dijkstra 算法。
• 在 数据结构 中存储多条路径。
• 对于每条路径，通过更改或删除边来创建变体。
• 继续搜索直到找到 K 条路径。

工作流程

• 查找最短路径： 该算法首先使用 Dijkstra 算法或任何其他可用算法查找源点和目标点之间的最短路径。
• 创建偏差： 通过刻意阻碍或改变 图 的部分，确保路径是不同的。
• 路径排序： 它记录所有已找到的最短路径，并在发现新路径时，将其从最短到最长进行排序。
• 继续此过程直到找到 K 条路径： 此过程将继续，直到发现 K 条不同的路径。

此算法的步骤

1. 初始化并找到第一条最短路径
   
   • 可以使用 Dijkstra 方法或其他算法找到源节点 s 和目标节点 t 之间的第一条最短路径。
   • 在 K 条路径的列表中，将此路径添加为第一条路径 P1。
2. 设置备选路径
   
   • 创建一个空的最小堆（优先队列）B，它将包含候选路径。每个潜在路径都应与先前识别的路径显着不同。
3. 迭代寻找 K-1 条路径
   从 2 到 K，对于每个后续的 k
   
   • 对于当前最短路径 (P k-1) 中的每个节点 (i)（除了最终节点 (t)）
   • 将 s 和 i 之间的段视为根路径。
   • 暂时删除图中属于先前发现的共享根路径的任何边。这可以避免行程在一段时间内沿着前一条路径前进。
   • 为了找到不同的路径（支路），再次从节点 I 到节点 T 应用该算法。
   • 为了创建完整的候选路径，将根路径与可能存在的任何支路连接起来。
   • 要将此新候选路径保存为潜在的最短路径，请将其插入最小堆 B。
   • 如果不再找到新的候选路径，则快速终止该过程。
4. 从堆中检索数据并存储最短路径
   
   • 将 B（最小堆）中的最短路径添加到路径列表，然后继续直到找到 K 条最短路径。
5. 这些路径的输出
   
   • 当找到 K 条路径或没有更多路径可扩展时，返回 K 条最短路径的列表。

算法

输入

• 图 G(V,E) 包含节点 V、边 E、源节点 s 和目标节点 t。
• 整数 K 用于指定所需的最短路径数量。

输出

• 这是从 S 到 T 的 K 条最短路径。

伪代码

说明

• Dijkstra 最短路径算法用于计算支路并确定初始最短路径。
• 偏差点： 路径上的每个节点都可能是不同路径的起点，因此每个偏差都会创建一个新路径。
• 候选最小堆： 它有效地以升序路径长度保存和检索候选路径。

时间复杂度

其中 n 是节点数，m 是边数，K 是所需的最短路径数，时间复杂度大约为 O(K⋅n⋅(m+nlogn))。

优点

Yen 的 K 最短路径算法的几个优点如下

• 灵活性： 它允许您识别多条路径，这在路径可能发生变化的动态系统（如网络）中非常有用。
• 效率： Yen 的方法高效地扩展了已建立的路径，而不是从头开始重新计算所有内容。

示例

让我们举一个例子来说明 C++ 中 Yen 的 K 最短路径算法。

输出

 
The 3 shortest paths from 0 to 4 are:
Path 1 (Cost: 3): 0 1 3 4 
Path 2 (Cost: 3): 0 2 3 4 
Path 3 (Cost: 3): 0 1 2 3 4   

结论

总而言之，Yen 的 K 最短路径算法 是一种简化的技术，用于识别加权有向网络中的多个唯一路径。Yen 的方法利用 Dijkstra 算法进行初始路径查找和路径偏差以生成变体，从而在源点和目标点之间找到多达 K 条最短路径。在确保每条后续路径都与之前路径唯一的同时，这种方法保持了最佳路径长度。Yen 的方法应用于网络路由、物流和交通规划，在需要替代路径的场景中提供了显著的灵活性。Yen 算法的 C++ 实现利用优先队列和邻接列表，高效且清晰，使其成为复杂路径查找要求的有用工具。