Yen算法和MPS算法

Yen算法和MPS算法是两种用于求解K最短路径问题的算法。它们的目标是在给定的图中找出K条最短路径。

Yen算法是一种改进的A*算法，它的核心思想是通过不断地从当前最短路径中删除一条边，然后再计算从起点到终点的最短路径，以此来寻找更短的路径。具体来说，Yen算法使用了一个优先队列来维护当前的最短路径，每次从队列中取出最短路径并计算其偏离路径，直到找到K条最短路径或者队列为空。Yen算法的时间复杂度在最坏情况下约为O(K * N^2 * lg(K * N))。

MPS算法是在Yen算法的基础上进行了优化。它使用了一种排序的策略来加快寻找偏离边的速度。具体来说，MPS算法将从每个点出发的所有边按照从该条边走向终点的最短距离进行升序排序，这样一来，寻找偏离边的时间就只有O(1)了。MPS算法的时间复杂度在最坏情况下约为O(N^2 * lgN + K * N)。

综上所述，Yen算法和MPS算法都是用于求解K最短路径问题的算法，它们的时间复杂度都与图的规模N和需要找到的最短路径数K有关。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [Yen 算法](https://blog.csdn.net/KZM2008/article/details/5460152)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]