Dial 环形桶最短路算法

距离可能一路增加到几万，并不意味着必须分配几万个桶。若每条边最多增加 C，刚结算一个距离后，当前尚存的候选都集中在宽度 C 的窗口里。Dial算法保留这个窄窗口，将同一批 C+1 个物理槽循环复用。

形式陈述

有限整数权与绝对距离游标

输入为邻接表图、合法源点，以及已知整数 $C\ge0$ ；每条边权是 $0\le w\le C$ 的整数。输出单源最短距离与父边，沿用Dijkstra的非负权结算语义。

建立 C+1 个桶 $B[0],\ldots,B[C]$ 。距离快照为 d 的记录放到

B[d\bmod(C+1)].

另维护从零开始、只增加的绝对距离游标 current。检查桶 $B[\text{current}\bmod(C+1)]$ ；若为空就增加游标，直到找到记录。槽号只表示存储位置，current 才表示正在处理的真实距离。两者混用，会在第一次回绕后把长路径误当成短路径。

带惰性旧项的可执行核心

下面假设输入已逐边核实，完整下载版会拒绝越界顶点、负权、非整数权和大于 C 的权。桶用双端队列的尾插与头删即可；不需要在每个桶内进一步排序。

python

from collections import deque
from math import inf

def dial(adj, source, maximum):
    dist = [inf] * len(adj)
    parent = [None] * len(adj)
    dist[source] = 0
    buckets = [deque() for _ in range(maximum + 1)]
    buckets[0].append((0, source))
    pending, current = 1, 0
    while pending:
        while not buckets[current % (maximum + 1)]:
            current += 1
        value, u = buckets[current % (maximum + 1)].popleft()
        pending -= 1
        if value != dist[u]:
            continue
        for v, weight in adj[u]:
            candidate = value + weight
            if candidate < dist[v]:
                dist[v] = candidate
                parent[v] = (u, weight)
                buckets[candidate % (maximum + 1)].append((candidate, v))
                pending += 1
    return dist, parent

pending 数的是尚未弹出的记录数，包括旧项，不是未结算顶点数。零权改进会把新记录放回当前桶，外层while自然继续处理同一距离；若不等当前桶清空就无条件增加游标，便可能错过这些新到的零权后继。

直觉

为什么取模没有丢掉优先次序

设刚有效结算的距离为 d。此前仍存的键不小于 d，又不大于前一次结算值加 C，因而不大于 d+C；本轮新键形如 d+w，也位于 $[d,d+C]$ 。旧项的快照虽可能已不是顶点的最佳距离，仍是当时合法生成的键，满足同样的上界。

从上次处理位置向前找下一桶时，游标经过的空桶证明那个绝对距离没有记录；所有存活键仍不小于当前游标，而原来的上界只会比 current+C 更紧。所以任意时刻的记录键落在 C+1 个连续整数内。

这一区间内的两个不同整数不可能模 C+1 同余，否则差至少为 C+1。故一个物理桶在当前窗口中只能代表一个真实距离，current 对应的非空桶必含当前最小键。由此恢复Dijkstra需要的最小键选择，而不是只凭“桶按编号排列”猜测正确性。

C+1 不能随意改成 C

当 C=2、当前距离为五时，合法窗口是 $\{5,6,7\}$ 。若只开两个桶，五与七会一起落在槽一，一个FIFO槽可能先吐出七；三个桶才能保持窗口内映射一一对应。C=0 时恰好只需要一个桶，所有可达距离都为零，不涉及取模零。

例子与边界

一次真正发生回绕的路径计算

顶点为 $s,a,b,c,t,z$ ，z 孤立，边为

s\to a:4,\ s\to b:1,\ b\to a:1,\ b\to c:5, \quad a\to c:0,\ a\to t:6,\ c\to t:2.

最大边权 C=6，因此仅开七个槽。结算 s 后生成 (4,a),(1,b)；结算 b 后改进为 (2,a),(6,c)；结算 a 后生成 (2,c),(8,t)。费用八的记录放在槽 $8\bmod7=1$ ，这时早先槽一的费用一已经弹出，current 为二，不会把八读成一。

Dial在绝对距离二处使用七个槽，费用八回绕到槽一但仍保存快照八 — 物理槽循环复用，绝对距离游标不回绕

接着结算 c，把 t 从八降到四。队列中还留下 a 的费用四、c 的费用六、t 的费用八三个旧项。它们被弹出时只减少pending，不扫描出边。最后距离为

(d[s],d[a],d[b],d[c],d[t],d[z])=(0,2,1,2,4,+\infty).

父边给出 $s\to b\to a\to c\to t$ ，费用 $1+1+0+2=4$ 。若计算所有距离并清空惰性队列，游标最后走到八；“最大最终最短距离只有四”不足以界定这个实现的实际扫描终点，因为旧快照还需要清理。

空桶扫描是实际成本

只有两点和一条权 C 的边时，算法为找到目标桶会跨过 C−1 个空距离。图很小不代表操作少；C巨大时，比较堆或radix heap更合适。给每条边做单位长度细分也会膨胀图，不能把整数权问题未经成本核算就称为普通BFS。

不可达顶点从未入桶。pending 归零就结束，不必把游标扫到某个预设最大值，也不能为了寻找孤立点而无限扫描。只有合法源点的单点图仍会初始化并结算源点；空图没有合法源点，应由输入接口拒绝。

推论与应用

记录、扫描与存储分开核算

以下时间界按单位成本RAM计：顶点下标、有限距离及中间距离和须装入可操作的机器字，加法、比较和所用队列基本操作按各自已声明成本收费。若权重或累计费用是任意长整数，须另计其位运算成本；这与radix heap页对Word-RAM及最高置位指令的要求相衔接。

每个顶点只有效结算一次，扫描出边共至多 m 次，成功松弛与入队共至多 m 次，再加源记录。每个记录只弹出一次，所有这些工作为 $O(n+m)$ ，n项初始化包含在内。

每个新键来自已结算顶点的最短路径再接一条边。非负权图的最短路径可选为简单路径，费用至多 $(n-1)C$ ，故新快照保守不超过 nC。游标不后退，累积增加次数至多 nC。连同 C+1 个桶的初始化，总时间为

O(n+m+nC),

其中 n≥1 已保证桶初始化的 C 被 nC 覆盖。写成常见的 $O(m+nC)$ 时必须额外处理 C=0，否则会把没有边却仍需初始化顶点表的工作漏掉。

本页惰性实现用 $O(n+m+C)$ 辅助空间：n项距离和父边、至多 m+1 份记录、C+1 个桶。经典有句柄版本把每个活动顶点只保存一次，减键时从旧双向链表摘下再移入新桶，空间可降为 $O(n+C)$ ；这需要稳定句柄与常数时间删除，不是把代码中的append换个名字便自动成立。

选择合适的专用队列

C=1时，活动候选只跨两个距离层，0–1 BFS将其压成一个deque，连环形槽游标也不用显式维护。一般小C适合Dial；若C很大但键是机器字整数，radix heap利用二进制差异跳过大片空范围。非整数边权则应回到适合其比较模型的队列，不能直接向桶号取整，否则路径优劣可能改变。

完成本页的手算应同时交出最终距离、费用四的真实路径，以及槽一先表示距离一、后表示距离八的时刻。再把 C 从六错误设置成五，指出哪条输入边违反了合同；这不是“可能精度下降”，而是支撑环形不混淆证明的前提已经失效。

参考资料

Robert B. Dial, “Algorithm 360: Shortest-Path Forest with Topological Ordering [H]”, Communications of the ACM 12(11), 1969, pp.632–633，DOI。
Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger and Roman Dementiev, Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox, Ch.10, 2019，§10.5.1，p313：C+1循环桶、活动距离窗口与有句柄减键版本。本文代码改用带快照的惰性记录，因此另计其空间与旧项扫描。

形式陈述 ​

有限整数权与绝对距离游标 ​

带惰性旧项的可执行核心 ​

为什么取模没有丢掉优先次序 ​

C+1 不能随意改成 C ​

一次真正发生回绕的路径计算 ​

空桶扫描是实际成本 ​

记录、扫描与存储分开核算 ​

选择合适的专用队列 ​

反向链接