2. 图与网络基础建模

网络流与最短路径问题，本质上都是在“图”上做计算。图不是画在纸上的示意图，而是一种把现实问题压缩成“点—边—权”三要素的数学结构。建模的第一步，就是判断现实对象中哪些是点、哪些是边、边上的权代表什么，以及方向、连通性和容量费用如何约定。这一步做对了，后面的算法才有意义；做错了，再精确的求解也只是在错误的模型上跑。

有向图与无向图：方向决定语义

无向图的边没有方向，表示两个对象之间“存在联系”，例如两台路由器之间的物理链路、两个城市之间的双向公路。有向图的边带箭头，表示“从 A 到 B”的单向关系，例如单行道、数据从采集端流向处理端、任务之间的先后依赖。同一个现实系统，用有向还是无向建模，结论可能完全不同：把单行道当成无向边，最短路径会算出一条实际走不通的路线。

约定上，有向图记为 G=(V,E)，V 是顶点集，E 是有向边集，边 (u,v) 表示从 u 指向 v。无向图的边 {u,v} 等价于两条方向相反的有向边，但在存储和算法中通常单独处理，避免重复计算。本节后续图示与公式统一采用“边 (u,v) 表示 u→v”的约定。

邻接矩阵与邻接表：两种存储的取舍

图在计算机里怎么存，直接影响算法效率。邻接矩阵用一个 n×n 的二维数组 A 表示，A[i][j] 存边 (i,j) 的权值，无边则记为无穷大（或 0，视约定而定）。它的优点是判断“i 到 j 有没有边、权是多少”只需 O(1)，适合稠密图；缺点是空间 O(n²)，当 n 很大而边很少时浪费严重。

邻接表为每个顶点维护一个链表或数组，只存它真正连出去的边。空间为 O(n+m)，m 为边数，适合稀疏图，也是绝大多数网络流与最短路实现的首选。缺点是查询任意两点间是否有边需要遍历该点的邻接表。下面给出一个带权有向图的邻接表结构示例（示例数据为教学假设）：

顶点: A B C D
边:   A→B 权4    A→C 权2
      B→C 权1    B→D 权5
      C→D 权8    C→A 权3
邻接表:
A: (B,4) (C,2)
B: (C,1) (D,5)
C: (D,8) (A,3)
D: (无出边)

对应的邻接矩阵中，A[0][1]=4、A[0][2]=2、A[1][2]=1、A[1][3]=5、A[2][3]=8、A[2][0]=3，其余为无穷大。可以看到，4 个顶点 6 条边时邻接表更省空间；若顶点增至上千且边仍稀疏，差距会非常明显。

路径、回路与连通性

路径是顶点与边交替出现、首尾相接的序列。若路径中所有顶点互不相同，称为简单路径；起点与终点重合的路径称为回路。最短路径问题通常只在简单路径中找最优解，因为含正权回路的路径去掉回路后会更短。连通性描述“能不能到达”：无向图中任意两点间存在路径称为连通图；有向图中分为强连通（任意两点互相可达）和弱连通（忽略方向后连通）。网络流建模中，源点到汇点必须存在路径，否则最大流为零，这是建模阶段就要检查的基本条件。

网络容量与费用：给边加上“约束”和“代价”

普通带权图只关心边的权值。网络流模型在此之上增加两个关键属性：容量 c(u,v) 表示这条边最多能承载多少流量，费用 w(u,v) 表示单位流量通过这条边的代价。容量约束是“硬约束”，流量不能超过它；费用是“软目标”，用于在可行流中挑出总费用最小的方案。最小费用最大流问题，就是先保证流量最大，再让总费用最小。建模时必须明确：容量和费用是定义在边上还是点上的，单位是什么（如“条/秒”“元/单位流量”），否则计算结果无法解释。

把实际问题抽象为带权图

抽象过程可以按四步推进。第一，识别实体：把需要区分状态或位置的对象定义为顶点，例如仓库、路口、设备、任务阶段。第二，识别关系：把实体之间可传递、可连接、可依赖的关系定义为边，并确定方向。第三，给边赋权：根据问题目标选择权值，求最短路径时权是距离或时间，求最大流时权是容量，求最小费用流时同时带容量和费用。第四，检查约束：确认源点、汇点、连通性、容量非负、是否存在负权边等前提是否满足。

以一个配送场景为例（示例参数为教学假设）：4 个配送节点 A、B、C、D，A 为仓库，D 为目的地，各路段为单向通行，距离如下：A→B 4 公里、A→C 2 公里、B→C 1 公里、B→D 5 公里、C→D 8 公里、C→A 3 公里。若只求最短距离，权值取公里数；若同时考虑每条路段的通行能力（如每小时最多通过 200 辆车），则需在边上再加容量属性，问题就从最短路升级为带容量的网络流。下图展示了该示例的带权有向图结构，以及邻接表与邻接矩阵两种存储视角的对应关系。

从图中可以直观看到：A 到 D 有两条候选路径，A→B→D 总权为 4+5=9，A→C→D 总权为 2+8=10，因此最短路径为 A→B→D，长度 9。若把 C→A 的权 3 也纳入考虑，A→C→A 构成回路，权为 5，属于正权回路，不会出现在最短路径中。这个判断过程正是建模后必须做的合理性检查：路径是否真实可走、回路是否为正、源汇是否连通。

需要强调的是，图模型一旦确定，后续算法只是在其上执行搜索或迭代。实际工程中，大量错误并非来自算法实现，而是来自建模阶段的约定不一致：同一张图里混用“有向”和“无向”语义、把容量当成费用、忽略负权边导致最短路失效。因此，在写任何代码之前，先用邻接表把示例图手工列一遍、用邻接矩阵核对一遍，是成本最低的验证方式。