1. 课程导入与问题地图

在开始学习网络流与最短路径算法之前，先建立一个清晰的问题地图，比直接记忆算法步骤更重要。本课程要解决的核心问题可以概括为一句话：在由节点和边构成的网络中，如何以最小的代价把资源从供给端送到需求端，或找到两点之间最优的通行路径。这句话看似简单，却覆盖了物流、通信、制造、能源、交通等大量真实系统的优化需求。

三个真实场景，同一类数学结构

先看物流配送。一个区域配送中心需要向 6 个门店补货，配送中心有 120 箱库存，各门店需求分别为 30、25、20、15、20、10 箱。仓库与门店之间、门店与门店之间存在若干条道路，每条道路有通行时间或运输成本。调度员真正关心的是：怎样分配每条线路上的货量，使总运输成本最低，同时每个门店恰好满足需求、每条线路不超过运力上限。这就是一个典型的最小费用流问题。

再看通信路由。一个企业骨干网由 8 台路由器和若干条链路组成，每条链路有带宽容量和当前时延。当从总部到分支机构的业务流量突然增大时，网络管理系统需要决定流量走哪几条链路，才能在不压垮任何一条链路的前提下，让端到端时延尽量小。这既涉及最短路径（选路），也涉及最大流（容量约束下的吞吐能力）。

第三个场景是项目调度。一个软件项目包含 9 项任务，任务之间存在先后依赖：需求评审完成后才能开始架构设计，接口定义完成后才能并行开发前后端。项目经理需要知道：项目最短需要多少天完成？哪些任务是关键任务，一旦延误就会拖累整个工期？把任务看作节点、依赖看作有向边、工期看作边权，问题就转化为有向无环图上的最长路径，也就是关键路径分析。

这三个场景表面上分属不同行业，但它们的数学结构高度一致：都由节点集合、边集合、边上的容量或代价、节点上的供需或约束构成。掌握这一层抽象，就能把算法从一个场景迁移到另一个场景。

课程技术主线

基于上面的问题地图，本课程按“建模—算法—实现—应用”四层推进。第一层解决如何把业务问题翻译成网络模型：识别节点、边、容量、代价、供需与约束，明确目标函数是最小化总代价还是最大化总流量。第二层进入算法原理：最短路径族解决“单点对单点”或“全源”的最优通行问题；最大流与最小割解决“网络最多能承载多少”的吞吐问题；最小费用流把两者结合，解决“在满足流量要求的前提下代价最小”的综合问题。第三层是实现与调参：用邻接表还是邻接矩阵、优先队列如何选、负权边如何处理、整数容量与浮点代价的精度问题。第四层是场景落地：把算法输出转回业务语言，例如“第 3 条线路分配 25 箱”“关键任务为架构设计与接口联调”。

学习目标

• 建模能力：给定一段业务描述，能独立画出网络图，标注节点角色、边方向、容量与代价，并写出流量守恒与容量约束。
• 算法选择：能根据边权是否含负值、是单源还是全源、是否需要容量约束，选择 Dijkstra、Bellman-Ford、Floyd、Dinic 或最小费用流算法。
• 手工推演：对 6～10 个节点的小规模网络，能手工执行算法迭代，写出距离标号或残量网络的每一步变化。
• 结果解读：能判断算法输出是否满足约束，识别不可行、无界、负环等异常情形，并解释其业务含义。

一个贯穿全课的小例子

为了让抽象概念有落脚点，先给出一个后续会反复使用的小网络。设节点 A 为配送中心（供给 40），节点 D 为需求点（需求 40），中间经过 B、C 两个中转点。边与参数如下（示例数据，用于教学推演）：

如果只问“A 到 D 哪条路单位运费最低”，答案是 A→B→C→D，单位费用 2+1+3=6 元，这是最短路径视角。但如果要运 40 箱，A→B 容量只有 30，B→C 只有 10，单靠这条最便宜路径最多只能送 10 箱。剩余 30 箱必须分流：A→B→D 可走 20 箱（受 B→D 容量 25 与 A→B 剩余 20 限制），A→C→D 可走 20 箱。此时总费用为 10×6 + 20×7 + 20×7 = 340 元。这个简单推演说明：最短路径不等于最优运输方案，容量约束会把问题从“选一条路”升级为“分配一组流”，这正是最小费用流要处理的情形。

常见误区与学习提醒

初学者最容易犯三类错误。第一类是方向混淆：把无向道路直接当成有向边处理，或在残量网络中忘记反向边代表“可撤销流量”。第二类是约束遗漏：只优化费用却忘记容量上限，导致方案在业务上不可执行。第三类是算法误用：在存在负权边的图上使用 Dijkstra，得到看似合理实则错误的最短距离。本课程会在相应章节逐一给出判别条件和修正方法。

网络流与最短路径不是一堆孤立算法的集合，而是一套把现实约束翻译成图结构、再用算法求解、最后翻译回业务决策的完整方法。带着“点、边、容量、代价、约束、目标”这六个关键词进入后续学习，会比死记步骤更有效。