K Shortest Paths算法之Yen algorithm

Yen’s算法是一种在图论中用于计算单源K最短无环路径的算法，该算法由Jin Y. Yen在1971年提出。这个算法的时间复杂度和空间复杂度都取决于用于计算偏离路径的最短路径算法。如果使用Dijkstra算法，那么时间复杂度为O(KN³)，采用Fibonacci堆计算可以优化到O(KN(M+NlogN))。

Yen algorithm的关键步骤

1.确定第一条最短路径：使用任何有效的最短路径算法（例如Dijkstra算法）从源点到汇点计算最短路径，将其作为第一条最短路径。

2.确定所有其他K最短路径：假设已经找到了从源点到汇点的所有路径，然后进行迭代，每次迭代都会找到所有的偏离路径，并选择一条最小长度的路径成为下一条最短路径。在这个迭代过程中，需要进行以下操作：

• 选择根路径：找到在前一条最短路径中的子路径，该子路径跟随前i个节点，其中i从1到k-1。
• 找到偏离路径：计算从偏离节点（即根路径的最后一个节点）到汇点的最短路径，这就是偏离路径。
• 将根路径和偏离路径加入到候选路径集合中：将根路径和偏离路径相加，形成一条完整的路径，然后将这条路径加入到候选路径集合中。

3.选择下一条最短路径：从候选路径集合中找到成本最低的路径，将其从候选路径集合中移除，并将其加入到最短路径集合中，然后继续下一次迭代。

4.重复步骤2和3，直到找到K条最短路径。

Yen algorithm图例

1.使用Dijkstra算法等，确定第一条最短路径A1=13，放入容器A，路径A1上的节点分别记为1,2,3,4

2.确定所有其他K最短路径
偏离节点为1时，选择节点1和2之间的链路weight变为无穷，R为根路径，S为偏离路径，计算出绿色的路径A2=14，先放入候选容器B

偏离节点为2时，选择节点2和3之间的链路weight变为无穷，计算出红色的路径A2=17，放入候选容器B

偏离节点为3时，选择节点3和4之间的链路weight变为无穷，计算出紫色的路径A2=16，放入候选容器B

所有当K=2时，计算出的A1和A2路径就如下，如果K>2时，那还要A2再单独拿出来，重复上面几步的运算

参考网站

Yen, Jin Y. (1970). “An algorithm for finding shortest routes from all source nodes to a given destination in general networks”. Quarterly of Applied Mathematics. 27 (4): 526–530. doi:10.1090/qam/253822. MR 0253822.

https://www.ams.org/journals/qam/1970-27-04/S0033-569X-1970-0253822-7/

https://en.wikipedia.org/wiki/Yen%27s_algorithm