双向 Dijkstra 与安全停止

μ是上界，两个队首提供另一侧证据 ​

每次更新μ都有两段已结算路径与一条真实连接边，因此μ从不小于真正最短距离。它只能告诉我们“已经有这么短的一条路”。

Dijkstra的结算性质还保证：尚未前向结算的可达顶点，到s的真实距离不小于α；尚未后向结算的顶点，到t的真实距离不小于β。否则该点更短的路径上会有一个更小的有效队列候选，违背队首最小性。这个下界针对未结算区域，不是说两边各自的全部距离都已求完。

为什么队首之和足以停止 ​

反设存在一条长度 $D<\mu \le \alpha +\beta$ 的s到t最短路P。对P上的某个顶点v，记沿P从s到v的长度为p，从v到t的长度为q，则p+q=D。若v两边都未结算，就同时有p≥α、q≥β，推出D≥α+β，矛盾。所以P的每个顶点至少属于一边已结算集合。

只要两边各自已开始扫描，s属于 $S_F$、t属于 $S_B$。沿P走，要么经过一个同时属于两集合的点，要么跨过一条从前向已结算点到后向已结算点的边。后一个端点结算并扫描该边时，算法已经比较过由它们连接出的路线；最短路的子路径也最短，候选费用恰为D，于是μ≤D，再次矛盾。这证明不存在比μ更短的路径。

若刚开始只有一边扫描过源点，μ仍无穷，两个有限队首不会触发上述有限上界停止。某侧此时已空，只可能它的起点没有可继续到达目标的路线，s=t已在入口单独处理。之后若一侧队列耗尽，另一侧起点早已结算：若有s到t路径，沿这条路径必有一个跨边候选被检查，最优路线已进入μ；若没有，μ保持无穷。

执行骨架与可运行版本 ​

若 s=t，返回零和 [s]
构建反向邻接表；初始化两个距离表、队列和结算集合
μ ← 无穷；连接证据 ← 空；方向 ← 前向
重复：
    丢弃两队头的旧快照与已结算项
    若任一队为空，退出
    若 min(QF)+min(QB) ≥ μ，退出
    从当前方向取最小有效项 (d,u)，结算 u
    若 u 在另一方向已结算，检查同点连接的完整费用
    对当前方向 u 的每条边：
        若边的另一端在对方已结算，检查跨边完整费用
        执行当前方向的严格松弛，更新父边并加入新快照
    切换方向
若 μ=无穷，返回无穷和空路径
否则沿保存的连接证据，拼接前向父链与反向后继链

完整Python实现与测试使用精确非负整数权，包含反图构造、旧项清理、父边恢复和零费用重复环删除。数学停止条件适用于精确非负实数权；浮点实现的舍入、溢出或NaN需要单独处理，不能把近似比较当成同一个证明。

同一整数图上，先找到八，再找到四 ​

使用Dial页的图：$s\to a:4,s\to b:1,b\to a:1,b\to c:5,a\to c:0,a\to t:6,c\to t:2$，另有孤立点z。按前向、后向交替：

清理旧项后，两队最小有效键都是二。$\alpha +\beta =4=\mu$，可以停止；两边并不需要各自结算t或s。连接边为 $a\to c$，两端父链拼成 $s\to b\to a\to c\to t$，真实费用四。孤立点z从未加入任一队列。

第一次相遇的点不一定在最短路上 ​

取 $s\to a:4,a\to t:4,s\to b:1,b\to t:6$。经a的路长八，经b的路长七。如果坚持等到一个点被双方都结算，a可以是最早的这样的点；直接返回“经过a的路”会得到八。

正确算法前向结算b时，t早已后向结算，跨边 $b\to t$ 已把μ更新为七。之后两队首均为四，$4+4\ge 7$，不必等到a处相遇就能返回七。

要区分两句话：第一次相遇后只返回经过相遇点的路径可能错误；若一直维护所有跨边的最好μ，经典的双方已扫描点相遇停止法本身也可以正确，只是常晚于队首之和停止。[1] 不能把第一种错误泛化成“任何相遇停止都错”。

反图不是可省的技巧 ​

只有边 $s\to a\to t$ 的有向链中，t没有出边。在原图从t向外搜会立即停住，却不表示s到t不可达；应沿反图的 $t\to a\to s$ 后退。无向图中每条边本来双向，这个区别不显眼，有向测试必须专门覆盖。

零权边与零权圈仍合法，队首之和可以等于μ，等号足以停。负边会破坏两侧结算下界，即使原图没有负圈也不能直接套用。只需要单对点查询是本页的接口；提前停止时，其他顶点的暂定距离通常尚未最优，不能把它们当作完整单源答案返回。

路径重建与成本 ​

以下时间界按单位成本RAM计：顶点下标、有限距离及中间距离和须装入可操作的机器字，加法、比较和所用队列基本操作按各自已声明成本收费。若权重或累计费用是任意长整数，须另计其位运算成本；这与radix heap理路单调整数键的 Radix HeapRadix heap · 基数堆 · Binary radix heap在新键不小于最后弹出键的承诺下，按与该键的最高二进制差异位分桶，通过严格降桶的重分配跳过大片空键域。页对Word-RAM及最高置位指令的要求相衔接。

前向父链从连接边起点u倒推到s；反向父链从连接边终点v按原图方向走向t。连接处只拼接一次。两段若再次经过同一顶点，形成的重复圈必为零费用，否则删圈会得到比已证明最优的μ更短的路；按首次出现位置删除这些零圈，可在O(n)时间得到简单路径。

每个方向至多结算n点、扫描m条边，反图构造为O(n+m)。使用二叉堆与惰性重复记录，插入、弹出总数为O(m+1)，两边合计的保守界是

时间与O(n+m)辅助空间。双向搜索在某些图上会少扫描许多顶点，但一般最坏渐近界并未因此改善；有向度分布偏斜时，也不保证两边探索范围一样大。

单元终结任务：用证书区分四种队列选择 ​

先对0–1 BFS页的零一图交出距离 $(0,0,0,0,1,\mathrm{\infty })$、到t的费用一路径、两份旧项的位置。再对本页整数图交出距离 $(0,2,1,2,4,\mathrm{\infty })$、到t的费用四路径，并完成三个独立核对：

1. Dial的槽一怎样先装距离一、后装距离八；解释为什么清空旧项后游标可到八而最终最短距离最大只有四
2. Radix heap的last从二改为四时，键4、6、4分别降到哪个桶，键八为何不用搬
3. 双向搜索在μ从八改为四后，给出两队最小有效键二和二，以及连接边 $a\to c$；证明此时停止无需等待双方在同一点结算

最后分别拒绝三种非法改动：让零一队列直接接受权二；让radix heap在last=4后插入三；让反向Dijkstra在原有向图沿出边行走。每次都应指出被破坏的不变量，而不是只说“换一种算法”。