网络流最大流算法

NetworkFlow Presentedby NetworkFlow 基本性质 对于网络 G u s t 1 容量限制 CapacityConstraints F x y C x y 2 流量守恒 FlowConservation F v x F x u 3 斜对称性 SkewSymmetry F x y F y x 讨论的前提 G为简单有向图网络 G u s t 中所有容量均为整数最大流 max flow 问题 就是求在满足网络流性质的情况下 源点s到汇点t的最大流量 Ford Fulkersonalgorithm Definition 1 剩余图 residualgraph 2 剩余容量 residualcapacity Ford Fulkersonalgorithm Definition 3 一条f可扩路 theaugmentingpath 剩余图中的一条s t路4 给定一个流f及剩余图中的一条路 或圈 P 沿P使f扩充r 对每一个e E P 若e E G 则令f e 增加r 设e0 E G 若e为e0的反向边 则令f e0 减小r注 此处的路径P不一定是可扩路 Ford Fulkersonalgorithm 输入 网络 G u s t 及各边容量输出 一条最大值的s t流f算法描述 1 初始时令所有边的流量f 0 2 求出剩余图 residualgraph 并在中找一条可扩路 theaugmentingpath P 若无可扩路 则终止 3 算出P路中各边剩余容量的最小值r 并沿P使f扩充r 转2 MaximumFlow MinimumCutTheorem Definition 1 s t流 指满足如下条件的流 a 源点流出量 0b 除s t点外 图G中的所有点流量守恒注 此处的s t流不单指图中特定的s t路s t流的值 源点s的流出量 2 s t割 即点集S指向点集T 此处T V G X 的边集 其中s S且t T割的容量 各边容量之和最小s t割 在G中关于u具有最小容量的s t割 MaximumFlow MinimumCutTheorem Definition MaximumFlow MinimumCutTheorem 任一个网络 G u s t 中 最大流的流量等于最小割的容量证明 1 任意一个流小于等于任意一个割 S T 即value F cap K 又可证 S T 中每条边的f都饱和 而 T S 中每条边的f都为零 故value F cap K cap K 综上 value F cap K Theorem 网络N G u s t 中的可行流f是N的最大流当且仅当N中不存在f可扩路必要性 若有可扩路P 沿P使f扩大即可充分性 设网络中不存在可扩路令S v V G 从源s到v有f可扩路 s 则与最大流最小割定理同样可证K S T 是网络中的一个割 且value f cap K 设F为最大流 K为最小割 则value f value F cap K cap K 故f即为最大流 K 即为最小割 Ford Fulkerson算法的劣势 Edmonds Karpalgorithm 最大流问题的第一个多项式时间算法 与Ford Fulkerson算法相比 改进之处在于第二步中P路径的选择 与其任选 不如选最短 边数最少 算法步骤 1 令所有边的流量f 0 2 在中找条最短可扩路P 若无 则止 3 算出P路中各边剩余容量的最小值r 并沿P使f扩充r 转2 复杂度 Edmonds Karp可在O m m n 内得解Edmonds Karp算法中无论边容量多大 最多增流m n 2次 m为边数 n为点数 每次增流用BFS最大为O m Dinic salgorithm Definition 分层图 levelgraph 首先 分层图是基于剩余图的其次 分层图会对所有顶点标号 与s的距离 最后 分层图中只存在这样的剩余边 u v dist v dist u 1 不符合这一规律的边全部删去 Dinic salgorithm Definition 阻塞流 blockingflow 网络 G u s t 对应的分层图中所有可扩路的并 即为阻塞流 Dinic salgorithm 算法步骤 1 令所有边的流量f 0 2 构造剩余图的分层图 levelgraph 3 在分层图中求一个阻塞的s t流 theblockingflow f 若f 0 则止4 用f 对f扩充 转2复杂度 在一定基础上可达O mnlogn 其中 n为点数 m为边数 详见课本153 Dinic算法的Example Dinic算法的Example Fujishigealgorithm 传说中的弱多项式算法对简单有向图G以及整容量可在O mn 时间内正确求解最大流问题 其中n为点数 m为边数 umax为最大边容量 详见课本153 Fujishigealgorithm Fujishigealgorithm 简单粗暴的说 1 每一次迭代都从s出发 s即v1 按当前的最大量 往t流a 只能往前流 v1 v2 v3 若到达t点 转2b 若途经某边剩余容量 则缩减 缩小一半向下取整 然后重新迭代 在对应剩余图的基础上除了 啥也没变 注 若 0 则终止2 从s出发的流成功到达t 假设为v6 沿途经过的顶点按顺序为 s v1 v2 v3 t v6 沿途经的边使流量f扩充 得到新的剩余图 转1 Push relabelmaximumflowalgorithm 推流 重标算法 Definition 1 超出量 FlowExcess 流入 流出2 活动点 active 除s t外 流入 流出的点 即超出量 0的点 Push relabelmaximumflowalgorithm 推流 重标算法 Definition 3 距离标号 distancelabels orheights a h s n h t 0 s和t的标号是固定的 b 剩余图中的所有边 u v 有h u h v 1 4 容许 admissible 边 剩余图中的边 u v 且h u h v 1 Push relabelmaximumflowalgorithm 推流 重标算法 算法步骤 1 令s的出边满流 其余边f 0 也可不置零 2 画出剩余图 令s的高度 height h s n 其余点h v 03 若有活动点 执行 设v为活动点 v点有容许边e 则push e v点无容许边 则relabel v Push e 在v