Eppstein的k条最短游走

把很多可能的下一次偏离装进一个堆 ​

在当前顶点v到t的树链上，每一点都可能离开树。直接把所有下一偏离一次性加入候选，分支数可达m；输出k条就可能为尚不需要的偏离付出过多成本。

给每个v准备一个堆H(v)，包含尾点在v到t树链上的所有偏离弧，以 $\mathrm{\Delta }$ 作为堆键。只先看堆根；其余弧通过堆孩子按需揭示。堆序理路二叉堆Binary heap用完全二叉树形状与父子堆序维护极值、常以数组隐式表示的数据结构。保证孩子不比父亲便宜，兄弟之间却不必完全排序。

不同v的树链共享后缀，H(v)也应该共享结构。若为每点显式复制整条树链的全部偏离，链形图上会重复保存大量相同内容。持久化路径复制理路持久化数据结构Persistent data structure · Persistence in data structures更新产生新版本而保留旧版本可访问性，并通过结构共享控制时间与空间的数据结构技术。让新增局部偏离后，旧H仍可用于其他起点。

两层堆的具体构造 ​

对每个v，把从v出发的非树弧整理成局部堆：取最小差价弧作为局部根，其余弧用Floyd法线性建一个二叉堆，并作为局部根的第三类附属孩子。局部根在这里额外单独存放，是为了后面的共享结构只合并根。

再建一个完全二叉根堆 $H_T(v)$，包含v到t树链上所有非空局部堆的根。若next(v)是树后继，则从 $H_T(\mathrm{next}(v))$ 的旧版本插入v的局部根；没有局部根就直接复用旧版本。t也须处理自己的出弧，不能把t默认改成吸收状态。

持久化插入按完全树的新位置走一条根叶路径。沿途保留较小键，把较大键继续往下送，并复制被修改节点；其他子树共享。根键不大于旧孩子，也不大于继续下送的键，所以堆序保持。最多复制 $O(\log (n+1))$ 个节点，因为根堆只含树链上至多n个局部根。

把每个根堆节点再接上其对应局部堆的剩余二叉子树，就得到H(v)。一个节点最多有根堆左孩子、右孩子和局部堆附属根三个孩子；局部子树节点只有两个孩子。每条偏离弧在单个H(v)里恰出现一次，堆序成立；跨不同版本共享节点不等于同一版本里重复放入同一弧。[1，§2.3]

同一图，简单路与游走的清单不同 ​

采用Yen页理路Yen的k条最短简单路径Yen's algorithm · Yen k shortest loopless paths · Yen最短无环路径算法固定根前缀、禁止已经输出的同根下一边并删除根上的旧顶点，以跨轮候选堆枚举不同的简单路径，证明覆盖性并区分游走枚举。的四点八弧图。朝t的树弧为0:s→a、1:a→t、3:b→t，距离为

非树弧差价为：2:s→b取一，4:a→b取一，5:b→a取一，6:s→t取三，7:t→a取四。比如弧5权一，其差价为 $1+2-2=1$；弧7权二，其差价为 $2+2-0=4$。

默认树路s→a→t费用三。只有偏离2时，得到s→b→t，费用四；偏离序列(2,5)得到s→b→a→t，费用五；序列(4,5)得到s→a→b→a→t，也是五，但已经不是简单路径。单独偏离7得到s→a→t→a→t，费用七，说明终点出弧不能省略。

下载程序前十二项的费用为

第五项的弧序列是(0,4,5,1)，而Yen的第五条简单路径是直达弧(6)，费用六。两份榜单不同不是某个算法出错，而是允许的输出对象不同。

零权环产生无限同价答案 ​

图只有s→a权一、a→a权零、a→t权一时，每个 $s\to a\to (a\to a{)}^r\to t$ 都是不同游走，费用都为二。任意有限k都能输出k条最低费用答案，但不存在“把全部费用二的游走输出完，再转入更贵答案”的有限时刻。

本页只承诺所请求的有限前k项，不承诺在存在无限低价游走时，按费用非降枚举最终会访问每个更贵游走。也不能把“第k条”误读成“第k个不同的费用值”。

同价时，下载实现固定弧ID、顶点队列次序、堆孩子次序，再用候选插入编号serial破平局。相同输入会得到相同输出序列；这不是完整弧序列的字典序。若要另一种全序，需重新说明无限同价集合上的排名是否存在，不能只换一个比较函数便假定一切不变。

显式输出为什么可能很长 ​

一个n点圈若可以反复经过，第i条游走可能已有 $\mathrm{\Theta }(ni)$ 条弧；完整展开前k条便可能需要 $\mathrm{\Theta }(n{k}^2)$ 个输出位置。隐式记录短，只表示共享了描述，不表示实际路线也短。

对平行弧，差价相同、端点相同仍是两个不同偏离候选，必须保留弧ID。若只求距离时曾合并平行弧，这项预处理在枚举时可能已经删掉合法答案，不能沿用而不说明。

从堆节点生成常数个候选 ​

把默认树路作为首个记录。对于一个已有偏离前缀P，H(v)中的节点h代表“接下来选h携带的弧e”，其中v为P最后偏离的头点；P空时v=s。此候选的总费用是 $c(P)+\mathrm{\Delta }(e)$。

它只生成两类后继：

• 替换最后一次偏离：对h的每个堆孩子h'，仍保留P，改用h'的弧；费用增加 $\mathrm{\Delta }(h^{\prime })-\mathrm{\Delta }(h)\ge 0$
• 追加一次偏离：将e正式加入前缀，再取 $H(\mathrm{head}(e))$ 的根；费用增加这个新根的差价，也非负

h最多有三个堆孩子，加上一个追加后继，分支最多四。初始树路只有一个后继，即H(s)的根；空堆不给后继。

这形成一棵可能无限、但每点有限分支的隐式堆序树。一个合法非空偏离序列的最后弧，在相应H(v)中有唯一位置：若不是根，唯一父状态来自替换边；若是根，唯一父状态来自去掉最后偏离的追加边。因此每条合法序列恰有一个状态，反复生成不会重复或漏掉游走。

主例中的堆节点与隐式状态分开绘制。灰箭头替换最后一次偏离，蓝箭头保留它再追加下一次偏离；对应差价均非负。

排序输出与路径恢复 ​

用另一个普通最小优先队列理路优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。保存已经发现、尚未输出的状态。取出最小状态，输出它的隐式记录，再加入上述至多四个孩子。任意尚未发现的状态，在通往根的路径上都有一个已入队祖先，祖先费用不大于它；所以队列最小项确为全局下一名。

隐式记录保存“此前偏离前缀记录的编号、最后一条偏离弧、总费用”。替换时仍指向同一前缀，追加时指向当前刚输出的记录。指针总朝更早记录，故不会形成记录环；不能把物理堆节点指针误当成完整偏离前缀，因为同一节点可供不同前缀复用。

解码时沿记录指针恢复偏离序列，再插入唯一树链。若显式输出总弧数为L，另付O(L+k)时间；零边游走也要一条分帧记录。这正是输出敏感计费理路输出敏感分析Output-sensitive analysis · Output-sensitive algorithms在明确输出接口后，同时用输入规模与实际输出规模刻画算法运行成本的分析方法。所要求的输出接口区别。

把预处理、选择和展开分开计费 ​

局部堆共包含至多m条弧，建堆为O(m)。每个顶点至多进行一次持久化根堆插入，共O(n log(n+1))时间与新增节点；距离、树、根指针还需O(n)。设单目标最短路预处理时间为 $T_{SP}$，则基础排序版的时间为

空间为 $O(m+n\log (n+1)+k)$。显式展开时再加O(L+k)时间。若可行游走少于k，上式中的k可换成实际输出数再加一个终止常数。

下载版以二叉堆跑反向Dijkstra，保守 $T_{SP}=O(n+(m+1)\log (m+2))$。若采用其他已证明的最短路实现，替换的是这一项，不改变偏离表示。费用、ID和计数器装入机器字时按单位成本计；反复绕圈会增加累计费用的位数，任意长整数不能无条件视作一条机器指令。

原论文进一步改善路径堆构造，并用Frederickson堆选择得到 $O(m+n\log n+k)$ 的隐式k个最小项集合，不要求这k项已按费用排好。[1，§3] 该优化不是把上述候选二叉堆的log k直接删掉；本页没有实现或自证这一高级选择算法，也不把它的界套到排序输出代码上。

终点与迁移 ​

手算差价表，解码(4,5)与(7)，指出前者重复a、后者先到t再离开。再给一条零权自环，说明有限k怎样继续得到不同的同价游走，以及为何“枚举后过滤成简单路径”可能一直停留在无限同价层。完整核验程序分别用原图上的独立k次取点队列核对费用、用实际弧序列核对解码与去重，不以有限测试代替一一对应证明。