最小费用最大流问题（Successive Shortest Path with Potentials 算法） 我将为您详细讲解最小费用最大流问题中的Successive Shortest Path with Potentials算法，这是一个结合了最短路径和网络流思想的经典算法。 问题描述 最小费用最大流问题是指在一个有向图中，每条边有容量限制和单位流量费用，我们需要找到从源点s到汇点t的最大流，并且使得总费用最小。这是网络流问题的一个重要变种，在实际应用中非常广泛，如物流运输、资源分配等。 算法核心思想 Successive Shortest Path with Potentials算法基于以下关键思想： 在残量网络中不断寻找从源点到汇点的最短路径（按费用计算） 沿着找到的最短路径推送尽可能多的流量 使用势函数（Potentials）来保证非负费用，从而可以使用Dijkstra算法 算法详细步骤 步骤1：初始化 创建残量图，初始时残量图与原图相同 初始化流量f(u,v) = 0 对所有边(u,v) 初始化势函数π(v) = 0 对所有顶点v 设置当前流量flow = 0，总费用cost = 0 步骤2：构建残量网络 对于原图中的每条边(u,v)： 正向边：容量c(u,v)，费用w(u,v) 反向边：容量0，费用-w(u,v)（当有流量时才创建） 步骤3：势函数更新与验证 势函数π必须满足以下性质： 对于残量网络中的所有边(u,v)，有： w_ π(u,v) = w(u,v) + π(u) - π(v) ≥ 0 这称为约化费用非负条件，它允许我们使用Dijkstra算法。 步骤4：主循环 当存在从s到t的增广路径时： 使用势函数计算约化费用： w_ π(u,v) = w(u,v) + π(u) - π(v) 在约化费用图上运行Dijkstra算法，找到从s到所有顶点的最短路径距离d(v) 如果d(t) = ∞，说明没有增广路径，算法结束 沿着找到的s-t最短路径推送流量： 计算可推送流量：Δ = min{残量容量沿路径} 沿路径推送Δ单位流量 更新：flow += Δ, cost += Δ × (实际路径费用) 更新势函数：π(v) = π(v) + d(v) 对所有顶点v 步骤5：算法终止 当无法找到从s到t的增广路径时，算法终止。此时flow是最大流，cost是最小总费用。 算法正确性证明要点 势函数的更新保证了约化费用始终保持非负 每次迭代都沿着当前最小费用路径推送流量 算法最终会找到最小费用的最大流 时间复杂度分析 每次迭代需要O(m log n)时间（Dijkstra算法） 最多需要F次迭代，其中F是最大流值 总时间复杂度：O(F × m log n) 示例说明 考虑一个简单网络： 顶点：s, a, b, t 边： s→a: 容量3，费用1 s→b: 容量2，费用2 a→t: 容量2，费用1 b→t: 容量2，费用3 a→b: 容量1，费用1 算法执行过程： 第一次迭代：找到路径s→a→t，推送2单位流量 第二次迭代：找到路径s→b→t，推送2单位流量 达到最大流4，总费用最小为2×1 + 2×1 + 2×2 + 2×3 = 12 这个算法通过巧妙地使用势函数，将可能含有负费用的图转化为非负费用图，从而能够高效地使用Dijkstra算法，是解决最小费用最大流问题的经典方法。