+— layout: post title: “最大流最小割原理与Ford-Fulkerson方法” date: 2019-10-11 excerpt: “以最短增广路径算法与Dinic算法实现” tag:
- 图论
- 算法 comments: true —
前言(?)
时光飞逝,岁月如梭(?),本来一直想写写并发来着,但总之是还没有写,最近上课又捡起了遗忘许久的算法导论,再看一遍网络流。
最大流最小割原理最开始在网络中应用(或许还有交通规划?),后来似乎也应用到图像处理中,在隔断两个网络时采取最小的代价。
Ford-Fulkerson方法是寻找最大流最小割的一种经典方法,其效率取决于实现也就是寻找增广路径的算法,比如后面将介绍两个基础好理解的算法,其实原理就是BFS和DFS,并比较它们的算法复杂度。
P.S. 本文是上课摸鱼时写的,本来有画图但是落在宿舍了,所以本文全篇没有配图,不好意思。
最大流最小割原理
最小割,其实就是希望在网络剪去一些边,使得图没有从源点s到汇点t的位置,且这些所剪取的边权重之和最小。数学上可以证明,最小割问题可以转换为最大流问题。
其实很好理解,就像从每个节点都有容量限制的水管网络中不停灌水,一次只流过一条路径,并且所灌的水单位小于等于这条路径中所有节点的容量,当这个水管网路无法再被灌水时,最大流就已经求出了,此时剪去节点对之间已经满了的路径,就可以得到网络的最小割。
最大流最小割原理:一个网中所有流中的最大值等于所有割中的最小容量。满足:
-
f是流网络G的一个最大流;
-
残留网Gf不包含增广路径;
-
G的某个割(S, T),满足f(S, T) = c(S, T).
Ford-Fulkerson方法
此方法的中心思想是清空所有顶点对间的流,接着通过残余网络寻找增广路径,直到无法找到可增加的增广路径。也就是上文说的往水管网路灌水的过程。
最短增广路径算法
最短增广路径算法借助了BFS,将网络分层(可能出现无法分层的情况,此时算法结束),每次在层次网络中找一条含弧数最少的增广路进行增广,实现步骤如下:
-
初始化容量网络和网络流。
-
构造残留网络和层次网络(对每个顶点标记层次),若汇点不在层次网络中,则算法结束。
-
在层次网络中不断用BFS增广,直到层次网络中没有增广路为止;每次增广完毕,在层次网络中要去掉因改进流量而 导致饱和的弧。
-
转步骤2。
算法复杂度分析
其实最短增广路径算法就分为两步:建立层次和寻找增广路径。
第一步中,每个层次可以用BFS遍历一遍,最多建立n个网络层,由于BFS的算法复杂度为O(m),所以建立层次对算法复杂度为O(n*m)。
第二步中,寻找增广路径,每次寻找增广路径时需要在遍历的同时修改流量,一次增广的复杂度为O(n+m),其中O(m)为BFS的花费,O(n)为修改流量的花费。所以在每一阶段寻找增广路的复杂度为O(m(m+n)) = O(mm)。因此n个阶段寻找增广路的算法总复杂度为O(nmm)。
Dinic算法
快下课了,就提一句带过吧。其实就是对最短增广路径对一种优化(?其实有时会更差),使用熟悉的DFS,时间复杂度为O(nnm)。