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

在边权非负时,从起点 出发,维护每个节点的暂定距离 。起点为 0,其余为无穷;每次把尚未永久确定且标签最小的节点 标记为永久,再对每条出边 做松弛:
为什么可以永久化?因为任何绕路到达尚未标记节点的路径,都至少要先经过一个标签不小于 的节点;非负边不会把总长度降回 以下。因此当前最小标签已是从起点到 的最短距离。负权边会破坏这个理由,不能直接套用。

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

流量要满足两件事:每条弧的流不超过容量,除源点和汇点外每个节点流入等于流出。找到一条从源到汇仍有剩余容量的增广路,沿路增加瓶颈容量
残量网络不仅保留正向剩余容量,也加入反向边,容量等于当前流量。反向边允许后续把一部分已有流撤回,重新改道;没有它,早期的路径选择可能把算法锁死。


当残量网络中已不存在从源到汇的路径时,取从源仍可达的节点集合 ,其余为 。所有从 指向 的原网络弧都已饱和,构成一个割;流值等于这些弧容量之和,于是当前流达到最大。这给出最大流—最小割证书。
若每条弧还有单位运输成本,目标变为最小化总费用,约束为流量守恒、容量和供需平衡。最短路、最大流和运输模型都可看成这个框架的特殊情形。建模时要明确节点净供给:供给节点流出减流入为正,需求节点则相反。

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