网络优化：路径、流与割

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

有向加权网络：节点、弧、长度和方向

最短路的标签法

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

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

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

Dijkstra 标签永久化与松弛边的过程

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

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

最短路路径回溯：前驱指针连接出完整路线

最大流与残量网络

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

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

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

增广路、瓶颈容量与残量网络的反向边

最大流过程中流量值和割容量的比较

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

最小费用流与网络模型

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

最小费用流的供给、需求、容量与单位费用

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

练习

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

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

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

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