先修:图的表示、DFS 和 BFS。
广度优先搜索(BFS)通常为每个顶点只记录一个父顶点。这足以还原一条最短路径,却会丢掉其他同样短的路线。要统计所有最短路径,我们同时维护距离和路径数;当另一条边进入一个已经发现的顶点时,根据它所在的层数分别处理。
本单元将 BFS 扩展到单位边长最短路径计数。
1. 明确统计对象
设 是有限有向图,顶点互不相同,不含平行边,每条边的长度均为 1。对于无向图,只要邻接表把每条边按两个方向各记一次,同一算法也适用。我们按顶点序列区分路径。由于每条边长都是 1,最短途径不可能重复顶点:删去非空环会使它变短。因此在这里,统计最短途径与统计最短简单路径的结果相同。
定义
(距离与最短路径数)
对源点 ,定义 dist[v] 为从 到 的最少边数,不可达时为无穷大。定义 ways[v] 为达到该距离的路径数。从 到自身恰有一条零边路径,因此 dist[s] = 0,ways[s] = 1;不可达顶点的路径数为零。
我们假设非负整数运算精确、使用先进先出队列,并通过邻接表访问图。如果图允许平行边,且按边的选择区分路径,就扫描每次出现的边并分别计数。如果路径按顶点序列区分,则必须先去除重复邻居;悄悄更改约定会改变答案。
2. 一个队列,两种情况
对每个 v:dist[v] = infinity;ways[v] = 0
dist[s] = 0;ways[s] = 1
queue = [s]
当 queue 非空:
u = pop_front(queue)
对 u 的每个邻居 v:
如果 dist[v] == infinity:
dist[v] = dist[u] + 1
ways[v] = ways[u]
push_back(queue, v)
否则如果 dist[v] == dist[u] + 1:
ways[v] = ways[v] + ways[u]
返回 dist, ways
首次发现 v 时,每条到 u 的最短路线都可以接上 u -> v,形成对 v 的第一份贡献。若 v 已被发现,且距离恰为 dist[u]+1,新贡献来自另一个最后前驱,必须加上。若 dist[v] 更小,此次延伸太长,不应贡献路径数。这个相等条件避免较长路线使计数虚增。
只有首次发现时才将 v 入队。这样做是安全的,因为先进先出 BFS 按距离非递减顺序处理顶点:移出任何第 层顶点之前,第 层的所有顶点都已移出。因此移出 u 时,所有可能作为到 u 最短路径末端前驱的顶点都已提供贡献。用于出边的计数已经完整。如果只在出队时标记,或每次收到等距离贡献都把 v 入队,就需要另外证明计数过程。
3. 为什么计数准确
定理
(计数 BFS 的正确性与代价)
设 与 如问题陈述一节所述。算法停止时,对每个顶点 ,dist[v] 是从 到 的最少边数(没有路径则为无穷大),ways[v] 是从 到 的最短路径数(没有路径则为零)。在每次精确运算代价为常数的模型下,运行时间为 ,辅助空间为 。
正确性部分在下面证明;代价界在代价一节推导。
证明
(对距离层归纳)
对距离 归纳。第零层的源点正确。假设距离为 的顶点在移出时,其计数都正确。对于距离为 的顶点 ,每条最短路径都有唯一的倒数第二个顶点 ,且 位于第 层。删去最后一条边得到到 的最短路径:否则用更短的路径替换该前缀,会得到一条到 的更短途径;再删去其中可能出现的环,会得到更短的简单路径。反过来,到这样一个邻居 的每条最短路径,接上 ,都是到 的最短路径。
不同前驱产生的路径集合互不相交,因为它们的倒数第二个顶点不同;图中也没有平行边。更新恰好对第 层的每条入边累加对应集合一次。先进先出顺序保证 移出前总和已经完整。归纳可证所有可达顶点的计数均正确。距离则由 BFS 首次发现的标准论证给出。
证明透视
为什么队列能确定最终路径数
只有从距离 到距离 的边能结束一条到第 层的最短路径。即使原图有环,这些边构成的分层图也是有向无环图。先进先出顺序在移出任何第 层顶点之前,先移出第 层的所有顶点,因此路径数用于延伸路径之前,所有有效前驱的贡献都已到达。
4. 例题详解
例题
(两条路线在一个顶点会合)
取边 、、、、、、,按列出的顺序处理邻居。移出 时发现 ,距离均为 1,各有一条路线。移出 时发现距离为 2 的 ,各有一条路线。移出 时发现 的距离已是 2,便再加一,得到 ways[c] = 2。移出 时发现 ,其 ways[t] = 2;移出 后再加一。
| 顶点 | ||||||
|---|---|---|---|---|---|---|
| 距离 | 0 | 1 | 1 | 2 | 2 | 3 |
| 路径数 | 1 | 1 | 1 | 2 | 1 | 3 |
到 的三条路线是 、 和 。改变邻居顺序可能改变哪条路线先被发现,但不会改变最终距离或路径数。
概念视角代数
路径数就是邻接矩阵的幂
设 为邻接矩阵,当 是边时 。矩阵 的 项,数的是从 到 、恰有 条边的途径数。令 :没有更短的途径,而恰有 条边的途径就是最短路径,所以 ,其中 是使该项非零的最小指数。在上面的图中, 的 行在 处为 、在 处为 ,而 。队列按层计算这些数值,过程中并不需要真正算出任何矩阵的幂。
例题
(必须忽略的后续边,与不可达顶点)
取边 、、、、、,另有一个孤立顶点 。移出 时发现距离为 1 的 和 ,各有一条路线。移出 时检查 :它已在距离 1,但 ,所以边 被忽略,ways[b] 保持为 1;接着发现距离为 2 的 ,ways[c] = 1。移出 时检查 ,它的距离恰为 ,所以 ways[c] 变为 2;再检查 ,它的距离是 0 而不是 2,所以构成环的边 被忽略。移出 后搜索结束。顶点 从未被发现,dist[z] 保持无穷大,ways[z] 保持为 0。到 的两条最短路线是 和 ;途径 有三条边,不计入。
例题
(路径数经瓶颈相乘)
取边 、、、、、、、。各层为 、、、、,距离为 0 至 4。移出 时发现 ,ways[m] = 1;移出 时再加一,ways[m] = 2。移出 时发现 和 ,两者都继承 ways = 2。移出 时发现 ,ways[t] = 2;移出 时再加 2,得 ways[t] = 4。结果是 :每条路线都经过 ,所以 之前的两个独立选择与 之后的两个选择相乘。若链上有 个这样的菱形,从 到末端有 条路线,可见计数增长得多快。
常见错误
(跳过每个已被发现的顶点)
普通 BFS 遇到进入已发现顶点的边就忽略,因为该顶点已有父顶点。若把这条规则照搬到计数算法,第一个例题中的第二条路线就会丢失:ways[c] 会停在 1 而不是 2,因为 被跳过。计数时,进入已发现顶点的边仍须检查,并且仅在 dist[v] == dist[u] + 1 时才作出贡献。
常见错误
(对每条进入 v 的边都累加)
相反的错误是对每条进入已发现顶点 的边 都写 ways[v] = ways[v] + ways[u],而没有相等测试。取边 、、:顶点 的距离为 1,恰有一条最短路径。移出 时检查 ,若没有该测试,ways[b] 会变成 2,把长度为 2 的途径 也算进去,而它并不是最短路径。
5. 代价与限制
每个顶点最多入队、移出各一次,每个可达顶点的每个邻接表条目扫描一次。初始化所有数组需要 ,因此在精确算术每次操作成本为常数的模型下,时间为 ,辅助空间为 (不包括邻接表存储)。路径数可能随顶点数指数增长。实际定宽整数可能溢出;任意精度加法的代价取决于位数,因此单位成本界并不描述位复杂度。若计数对 取模,输出只是余数:余数为零并不证明不存在最短路径。
本证明依赖所有边长均为 1。边权不等时,普通 BFS 的层数未必是最短距离层,必须使用适当的带权最短路径方法,并证明计数何时最终确定。特别是零权边或零权环会带来额外问题,不在本章统计约定内。
反例模式
按 BFS 层数计数对带权边不成立
断言:边有正权时,同一算法同样能统计最短路径数,只要把 dist 理解为带权距离。取边 、、、,权均为 1,以及权为 3 的边 。从 到 的带权最短距离是 2,恰有两条路径达到: 和 ;直接的边代价为 3。算法数的是边数而不是权:移出 时发现 、、,距离都是 1,ways[t] = 1,之后的边 与 因 被忽略。它报告距离为 1、路径数为 1,所指的是那条直接的边,而它根本不是带权最短路径。单位边长的假设正是使边数等于距离的条件,因此这个定理不能套用于此;必须使用带权最短路径方法。
6. 即时检查
快速检查
(在第一个例题中,若删去边 ,dist[t] 与 ways[t] 各是多少?)
解答 · 答案
删去 后剩下路线 和 。 的距离仍为 3,ways[t] = ways[c] = 2。
快速检查
(当边 连接两个 dist[u] == dist[v] 的顶点时,为什么不把 ways[u] 加到 ways[v]?)
解答 · 答案
到 的最短路径接上 后有 dist[u] + 1 条边,比 dist[v] 多一条。它是到 的途径,但不是最短路径,所以不能计入。
快速检查
(对边 、、、、、、、,求 dist[t] 与 ways[t]。)
解答 · 答案
各层为 、、、,所以 dist[t] = 3。 与 都可由 和 到达,所以 ways[c] = ways[d] = 2,ways[t] = 2 + 2 = 4。换个说法,一条最短路径要在 中选一个、在 中选一个: 条。
快速检查
(算法中的所有计数都对 1000 取模,而 ways[t] 报告为 0。能否断定 不可达?)
解答 · 答案
不能。恰好 1000(或 2000 等)条路径同样会得到余数 0。是否可达要看 dist[t] 是否有限,而不是看余数。