K条最短路径算法(KSP, k-shortest pathes)：Yen's Algorithm
参考：
- K最短路径算法之Yen's Algorithm
- Yen's algorithm
- 基于网络流量的SDN最短路径转发应用
K条最短路径算法：Yen's Algorithm
算法背景
K 最短路径问题是最短路径问题的扩展和变形。1959 年，霍夫曼(Hoffman) 和帕夫雷(Pavley)在论文中第一次提出k 最短路径问题。 k 最短路径问题通常包括两类：有限制的k 最短路问题和无限制的K 最短路问题。 前者要求最短路径集合不含有回路，而后者对所求得的最短路径集合无限制。
算法简介
Yen's算法是Yen 在1971 年提出的以其名字命名 的Yen 算法。Yen's算法采用了递推法中的偏离路径算法思想，适用于非负权边的有向无环图结构。
算法思想
算法可分为两部分，算出第1条最短路径P(1)，然后在此基础上依次依次算出其他的K-1条最短路径。在求P(i+1) 时，将P(i)上除了终止节点外的所有节点都视为偏离节点，并计算每个偏离节点到终止节点的最短路径，再与之前的P(i)上起始节点到偏离节点的路径拼接，构成候选路径，进而
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！