“采用Yen页的四点八弧图。朝t的树弧为0:s→a、1:a→t、3:b→t，距离为”
一条最短路线不够时，可以要求第二条、第三条备用路线。但“不同”不等于“互不相交”：两条答案可以共用大部分边；本页只要求每条路线内部不重复顶点，且不同答案的边序列不同。若应用要求边不交、绕开特定风险区或长度差很大，那是额外约束。
形式陈述
简单路径与输出身份
沿用最短路问题的可加成本与弧身份模型，输入为有限有向图、源s、终点t、非负边权及请求数k。每条弧有独立ID，允许平行弧；输出按成本非降排列的至多k条简单路径，即顶点序列没有重复。两条路径按弧ID序列区分：同一对端点间的两条平行弧，仍可能给出两个不同答案。
同成本路径分别计数，平局可任意，但实现应采用固定规则。下载版本按候选插入编号破除成本平局，不承诺顶点序列的字典序。k=0返回空；s=t时唯一简单路径为零边路径。若从s到t只有q<k条简单路径，就恰输出q条并结束。
本页受限最短路子程序使用Dijkstra，因此权重非负。Yen原方法可以搭配其他适用的最短路子程序，本页没有因此允许把负边直接交给Dijkstra。[1]
根前缀与偏离后缀
保存已输出列表A和跨轮保留的候选最小堆B。先求一条最短路径
要从u重新找后缀，作两种临时限制：
- 删除R中除u外的全部顶点，防止后缀回到根上造成重复顶点
- 对A中每条以完全相同弧前缀R开头的路径，禁止它紧接R的下一条弧，防止再次走出已输出的同根路径
在这张受限图上，从u到t求一条最短简单后缀S。若存在，将R与S在u处拼接成候选，放入B；u只出现一次。所有限制只用于当前偏离点，下一个点需要自己的限制集合，原图本身不被永久删除。
完成P的全部偏离后，从B取成本最小且未输出的候选作为下一条。下载实现按完整弧ID元组去重，避免同一候选被不同轮次多次生成；若B空，算法终止。
可执行骨架
text
若 k=0，返回空
P ← 原图中一条最短 s→t 路径；若不存在，结束
A ← [P]；B ← 空最小堆
重复直到 |A|=k：
对 A 的最后一条路径上的每个偏离点 u：
R ← 从 s 到 u 的根前缀
禁止 R 中 u 以前的顶点
禁止 A 中所有同根路径紧接 R 的下一条弧
S ← 限制图中一条最短 u→t 后缀
若 S 存在且 R+S 未生成过，把它加入 B
若 B 为空，结束
从 B 取最小候选，加入 A 并输出“所有同根路径”不能缩成“仅上一条路径”。完整标准库实现维护前缀到已输出下一弧的表，避免每次从头扫描A；零权边用严格松弛与父边恢复，不靠首次发现就锁定距离。
直觉
Lawler首次差异分区说明，一条新答案应在某个最早位置离开已知前缀。路径不能把后面各坐标当作独立比特，因为后缀必须连通，而且不能重新经过前缀顶点。两种临时限制分别承担“与已有答案不同”和“整条路径仍简单”的责任。
候选堆B保存的是以前所有轮次留下的备选项。新一轮只是给它增加来自最新答案的偏离，不是重新开始搜索。即使最新答案的所有新偏离都失败，早先留下的候选仍可能是下一条最短路径。
固定一个根前缀后，只需保存当前约束下的最短后缀。更贵的同根答案暂时不必全部生成；当当前代表被输出，它会把相应的下一边加入禁止表，后续偏离就会揭示这一根下的新代表。
例子与边界
四点图中的五条简单路径
用顶点
| ID | 弧 | 权重 |
|---|---|---|
| 0 | s→a | 1 |
| 1 | a→t | 2 |
| 2 | s→b | 2 |
| 3 | b→t | 2 |
| 4 | a→b | 1 |
| 5 | b→a | 1 |
| 6 | s→t | 6 |
| 7 | t→a | 2 |
最短路径为s→a→t，成本三。以s为偏离点，禁止弧0，最短候选是s→b→t，成本四；以a为偏离点，删除s并禁止弧1，得到a→b→t，与根s→a拼成另一条成本四路径。
下载程序依次输出：
| 次序 | 弧ID序列 | 路径 | 成本 |
|---|---|---|---|
| 1 | (0,1) | s→a→t | 3 |
| 2 | (2,3) | s→b→t | 4 |
| 3 | (0,4,3) | s→a→b→t | 4 |
| 4 | (2,5,1) | s→b→a→t | 5 |
| 5 | (6) | s→t | 6 |
请求二十条也只有这五条。弧7可以出现在允许重访t的游走中，却不会出现在以t为终点的简单路径里；到达t后再离开、最后返回t会重复t。
同根禁止与删除旧顶点都必要
已输出s→a→t和s→b→t后，在空根s处必须同时禁止弧0与2，否则又得到前两条之一。在根s→a处，禁止的是已输出同根的下一弧；不能因为别的根用过某条边，就把它全局删除。
处理根s→a→b时，需删除s和a。若只禁止下一弧b→t而保留a，后缀可能选b→a→t，拼接得到s→a→b→a→t，虽然费用有限，却已经重复a。这正是简单路径和可重复游走两种接口的分界。
零圈和同价答案
若a→b、b→a的总权为零，允许重复点的游走可以绕任意多圈，产生无限多个同成本答案；简单路径仍只有有限多个，因为每条最多含n−1条弧。先枚举游走再丢弃含圈项，可能永远等不到更贵的下一条简单路径，因此不能当作本算法的替代。
同成本不是重复判据。两条成本四的路线都应保留；若只用成本作为去重键，就会漏解。同样，在多重图中用顶点序列去重会合并不同平行弧产生的路径，改变了本页按弧ID区分的合同。
推论与应用
为什么候选堆没有漏掉下一名
每个生成候选都由简单根与避开根上旧点的简单后缀拼成，因此合法。它的下一弧又避开所有当时已输出同根路径，所以不会等于当时A中的任何一条；完整ID序列去重避免候选之间重复。
对任意尚未输出路径Q，在当前A中找与Q共有最长弧前缀R的路径；若不止一条，取其中最近输出者P。这个共同前缀必在Q到达t之前结束，否则另一条简单s→t路径不可能再延长它。
P被展开时，Q从R下一步使用的弧没有被禁止：若某条已输出路径也使用它，就会与Q共享更长前缀，和R的选择矛盾。Q的后缀也不经过根上的旧顶点，因为Q简单。因此Q是该受限问题的一个合法完成，算法生成的最短候选C满足
C不可能已经被输出：P之前的同根下一弧均已禁止；若C在P之后输出，则C也有前缀R，与“P为最近输出的同根路径”矛盾。故C仍在B中，或相同C早已在B中。B的最小项不贵于任意未输出Q，于是确为下一名；B空也就证明没有未输出路径。
这份论证需要累计的A与跨轮的B。只保留最新一轮候选，会把仍负责某些未输出Q的旧代表丢掉。
子程序次数与显式存储
设n≥1、m为带ID的弧记录数，实际输出q条。每条简单路径至多有n−1个偏离点；含第一次最短路调用，完整运行的子程序次数不超过
若在第k项后立即停止，最后一项不必展开，界还可略降。一次受限Dijkstra的时间记为T，包含建图或扫描过滤条件、n项初始化与父边恢复。使用二叉堆惰性记录，可保守取
下载实现显式保存长度O(n)的路径和前缀。前缀表、候选集合采用哈希表，按期望常数探测计，逐个构造/哈希长元组仍花O(n)。堆用标量成本加serial比较，因此一个候选的堆操作只付对数成本。保守总界为
空间为
所有费用加法、比较、ID和计数器在单位成本RAM口径下收费；大整数或精确实数表示须另计。一般数据结构上的最坏字典成本也不能从Python哈希表的期望口径直接推出。
终点与迁移
手算前两轮：第一条产生哪两个成本四候选，第二轮在s处为何同时禁止0与2，以及s→a→b→t为何必须留到下一轮。然后增加一条与弧2同端点同权、但ID不同的平行弧，解释应新增哪些不同路径。
若只要求若干条低成本游走，Eppstein的偏离堆能避免每次重跑最短路；若要求路径互不共边，本页按排名给出的五条答案又不满足该新目标。先确定输出对象，再选择枚举结构。
参考资料
- [1] Jin Y. Yen, Finding the K Shortest Loopless Paths in a Network,Management Science17(11),1971,712–716，§3–5：根/偏离、同根弧禁用、候选列表跨轮保留及正确性。此为MIT教师保存的原论文扫描。
- David Eppstein, k-best enumeration,2014，§2.3、§3：分区技术及简单路径与允许圈的路径问题。本文保留弧ID，单列零圈、显式元组与字典成本，不套用其他表示的空间界。