网络优化：路径、流与割

把仓库、工厂、车站画成点，把道路、管道或通信链路画成有向边，很多看似不同的问题会显露出同一个结构。网络优化的价值在于：除了目标和约束，它还利用图的局部连接关系，避免把所有变量都当成一团没有结构的矩阵。

最短路的标签法

在边权非负时，从起点 $s$ 出发，维护每个节点的暂定距离 $d(v)$。起点为 0，其余为无穷；每次把尚未永久确定且标签最小的节点 $u$ 标记为永久，再对每条出边 $(u,v)$ 做松弛：

$$d(v)\leftarrow\min\{d(v),d(u)+w_{uv}\}.$$

为什么可以永久化？因为任何绕路到达尚未标记节点的路径，都至少要先经过一个标签不小于 $d(u)$ 的节点；非负边不会把总长度降回 $d(u)$ 以下。因此当前最小标签已是从起点到 $u$ 的最短距离。负权边会破坏这个理由，不能直接套用。

例题：改变终点不必重算全部结构

若网络有 $s\to a$ 长 4、$s\to b$ 长 2、$b\to a$ 长 1、$a\to t$ 长 5、$b\to t$ 长 9，则标签依次为 、通过 更新 、再更新 。路径是 ，不是直接选择看起来最短的单条边。

最大流与残量网络

流量要满足两件事：每条弧的流不超过容量，除源点和汇点外每个节点流入等于流出。找到一条从源到汇仍有剩余容量的增广路，沿路增加瓶颈容量

$$\Delta=\min_{(u,v)\text{在路上}}r_{uv}.$$

残量网络不仅保留正向剩余容量，也加入反向边，容量等于当前流量。反向边允许后续把一部分已有流撤回，重新改道；没有它，早期的路径选择可能把算法锁死。

当残量网络中已不存在从源到汇的路径时，取从源仍可达的节点集合 $S$，其余为 $T$。所有从 $S$ 指向 $T$ 的原网络弧都已饱和，构成一个割；流值等于这些弧容量之和，于是当前流达到最大。这给出最大流—最小割证书。

最小费用流与网络模型

若每条弧还有单位运输成本，目标变为最小化总费用，约束为流量守恒、容量和供需平衡。最短路、最大流和运输模型都可看成这个框架的特殊情形。建模时要明确节点净供给：供给节点流出减流入为正，需求节点则相反。

网络约束矩阵有特殊的“一个弧只连接两个节点”的结构。在整数供给和容量下，许多网络流模型会出现整数最优解；这不是“算法碰巧给出整数”，而是矩阵结构带来的整数性。遇到一般整数模型，不要擅自把这个性质推广过去。

练习

1. Dijkstra 算法为什么要求边权非负？

查看解答

它把当前最小的未永久标签视为最终距离，依据是之后经过其他节点不会通过负边把距离降得更低。若有负边，这个永久化依据失效。

2. 一条增广路上的剩余容量为 7、3、5，最多能增加多少流？

查看解答

增加量是瓶颈最小值 $\Delta=3$。增加 3 后，容量为 3 的弧在该方向上耗尽。

3. 残量网络中的反向边有什么作用？

查看解答

反向边允许算法撤回一部分已经发送的流，从而把流量重新安排到更好的路径。它记录的是“可取消的既有决策”，不是原图中新建了一条真实道路。

1

找到一条从源到汇的路径，就能断言当前流已经最大。

正确错误