ISAP · 距离标号 · gap 优化

ISAP：距离标号与就地重标号

Dinic 的每个相位都从一次完整 BFS 开始。相位之间残量网络只变了一部分（被推满的那几条边），层次图却整张作废重建。ISAP（improved shortest augmenting path）保留 Dinic 的最短增广路思想，却把分层从「每相位一次」压到「全程一次」：走不通的时候不重建全图，只把当前这个点的标号抬高一格。

1 · 从层号到距离标号

Dinic 的层号量的是「从源点走了多远」，ISAP 换成反方向。

定义 4.1（距离标号） 残量网络上的函数 $d[v]$ 称为距离标号，若 $d[t] = 0$ ，且对每条残量边 $(u, v)$ （残量 $> 0$ ）都有

d[u] \le d[v] + 1

标号合法时 $d[v]$ 是 $v$ 到汇点 $t$ 的最短距离的下界：沿任一条 $v \to t$ 的残量路逐边套用上式即得。

这个「 $\le$ 」是全页的枢纽。反向 BFS 能让每个 $d[v]$ 取到精确的最短距离，但算法运行中并不需要精确——只要不变量不破，标号就仍是合法下界，仍能用来判断哪条边值得走。

定义 4.2（允许弧） 残量边 $(u, v)$ 满足 $d[u] = d[v] + 1$ 时称为允许弧。沿允许弧走一步，到汇点的距离下界恰好减 1。

允许弧构成的子图里，任一条 $s \to t$ 的路长度都等于 $d[s]$ ，即当前残量网络中最短增广路的长度。Dinic 的层次图与它是同一个东西的两种坐标：前者按「离源多远」分层并逐相位重算，后者按「离汇多远」标号并终身维护。

	Dinic 层号	ISAP 距离标号
量什么	$s$ 到 $v$ 的最短距离	$v$ 到 $t$ 的最短距离
BFS 次数	每相位一次，至多 $V - 1$ 次	全程一次
走不通时	本相位结束，整张重建	抬高当前点标号，回退一步
终止条件	BFS 到不了 $t$	$d[s] \ge n$

2 · 主循环的动作

主循环维护一个从源点出发的路径栈，以及一个「当前所在点」 $u$ 。每步只做三件事之一。

注 · 三个动作的分工。

advance： $u$ 有允许弧 $(u, v)$ ，压栈并把 $u$ 移到 $v$ 。
augment： $u$ 到达汇点，沿栈上各边取瓶颈推流。
retreat： $u$ 没有允许弧，把 $d[u]$ 抬到 $1 + \min{d[v]} $（$ v$ 取遍残量邻居），然后回退一步。

retreat 抬高后不变量仍然成立：新值取的就是「最低可达邻居 $+ 1$ 」，对每条残量出边都满足定义 4.1。抬高只会让标号更紧，不会让它越过真实距离，算法全程都在合法标号上工作。

retreat 回退的是搜索位置，不是已推的流量：路径栈会退、标号会抬，但每条边上的流量一步都不退。这与回溯搜索里的「撤销一个选择再换一个」是两回事。那种回退会让已取得的进展作废，代价直接体现为搜索树的分支数；而 retreat 每次都伴随标号严格抬高，标号单调不减且有上界，回退次数有界。撤销与回溯那页把这条线索单独拉出来讲。

增广之后的续走位置是 ISAP 省下重复工作的地方。一次增广会让路径上至少一条边饱和，但饱和点之前的前缀仍然全是允许弧。算法把 $u$ 退回到最靠源的那条饱和边的起点，前缀原样保留，而不像 Ford-Fulkerson 系那样退回源点从头找。

当前弧指针与 Dinic 那页 §2 一样：每个点记住自己的边试到第几条，被判定走不通的边在标号未变前不再回看。标号一旦抬高，指针重置为 0——因为允许弧的判据变了，先前跳过的边可能重新可用。

图 2-1 · ISAP 在 Dinic 那张多相位网上的完整执行。节点下方

d

为距离标号，橙色描边为当前所在点；下方计数桶给出每个标号层的点数。可逐帧对照 advance / retreat / augment 三种动作与代码行的对应。

3 · gap 优化的判死条件

至此 ISAP 的收敛全靠 $d[s]$ 一格格抬到 $n$ 。有一个判据能提前很多步结束。

定理 4.3（gap 判据） 设 $cnt[k]$ 为当前标号为 $k$ 的点数。若存在 $0 \le k < d[s]$ 使 $cnt[k] = 0$ ，则残量网络中不存在 $s \to t$ 的增广路。

证明设存在增广路 $s = v_0 \to v_1 \to \dots \to v_m = t$ 。每条边都是残量边，故由定义 4.1 有 $d[v_{i}] \le d[v_{i+1}] + 1$ ，即沿路标号每步至多降 1。又 $d[v_0] = d[s]$ 、 $d[v_m] = 0$ ，路径把标号从 $d[s]$ 降到 $0 $，每步降幅不超过 1，所以 $\{0, 1, \dots, d[s]\}$ 中每个值都被路上某个点取到。这与 $cnt[k] = 0$ 矛盾。∎

实现只需在 retreat 分支里加一行：抬高 $d[u]$ 之前先把 $cnt[d[u]]$ 减 1，减完为零就把 $d[s]$ 置为 $n$ 并跳出循环。代价是维护一个长度 $n$ 的计数数组。

图 3-1 · 搁浅网上 gap 优化的开关对照。这张网的汇入被

a \to t

与

b \to t

卡在 5，源点却能灌出 7，多余的 2 个单位注定退回；

a \to d \to e \to b

是一条通不到汇的绕路。可切换 gap 开关，观察计数桶哪一层先归零，以及末列的 retreat 次数差。

收益随网络结构变化很大。搁浅网上开 gap 是 12 帧、关 gap 是 22 帧，retreat 从 9 次降到 2 次；而在图 2-1 那张网上，两者是 18 帧与 19 帧，只差一帧。gap 优化真正省下的是「把搁浅在死支路上的超额一级一级抬回源点」这段过程，网络里没有这种结构时它近乎白装。

4 · 帧数与复杂度的错位

写本页时踩了一个坑，值得记下来。图 2-1 与 Dinic 页的图 3-1 跑的是同一张网，Dinic 用 7 帧、ISAP 用 18 帧，看上去像是 ISAP 慢了一倍多。这个对照是错的：两个引擎的帧粒度不同。dinicSteps 一帧记一整条阻塞路（一次 DFS 从源走到汇再推流），isapSteps 一帧只记一次 advance 或 retreat 这样的单步微操作。把 ISAP 的帧按「到达汇点」切段，得到的增广次数是 3，与 Dinic 在这张网上的 3 条阻塞路一致。最后改的是这一节的叙述，不是引擎——单步粒度细本身是本页想要的，它让 retreat 与 gap 看得见。

搁浅网的构造也是试错的产物。最初写的是一张「死胡同网」：汇入被单条 $c \to t = 2$ 卡住，另有一条支路彻底通不到汇。它在 ISAP 侧表现不错（6 帧对 11 帧），但拿去跑 HLPP 时 gap 一次都没触发。开了 global relabel 之后，通不到汇的点全部停在高度 0，gap 需要的「中间高度层」根本不存在。改成现在这张网（先让 $a \to t$ 饱和，迫使 $a$ 抬升，中间层才出现）两页才都用得上同一张网。

理论复杂度上，ISAP 与 Dinic 同为 $O(V^2E)$ ，gap 优化不改变这个上界，它省的是常数。实测里 ISAP 通常快于 Dinic，因为省掉了每相位一次的全图 BFS；但这属于常数层面的经验，不是渐进意义上的改进。

「ISAP」这个缩写主要流行于竞赛社区，学术文献里一般不这么叫。算法本体是 Ahuja–Orlin 的距离标号最短增广路算法 [1]，gap 启发式作为独立技巧被单独讨论 [2]。没找到把这两者合起来命名为 ISAP 的原始出处。

5 · 参考文献

Ahuja, R. K., & Orlin, J. B. (1991). Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems. Naval Research Logistics, 38(3), 413–430.
Derigs, U., & Meier, W. (1989). Implementing Goldberg's max-flow algorithm: A computational investigation. Zeitschrift für Operations Research, 33(6), 383–403.
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.