最大流算法-最高标号预流推进(HLPP)
时间: 2023-10-12 11:54:55 浏览: 57
最高标号预流推进算法(High-Level Preflow Push, HLPP)是一种常用的最大流算法。它的基本思想是将节点按照高度分类,按照高度从高到低进行推进流量,同时维护一个优先队列,以保证高度最高的节点优先处理。该算法可以在$O(V^2\sqrt{E})$的时间复杂度内求解最大流,其中$V$和$E$分别表示节点数和边数。
算法的具体步骤如下:
1.初始化:将源点$s$的距离$d(s)$设为$|V|$,其余节点的距离$d(v)$设为$0$,并将源点的流量$f(s,v)$设为该边的容量$c(s,v)$。
2.进行预流推进:对于每一个非汇点$v\neq t$,如果$f(s,v)>0$,则将流量$f(s,v)$推进到邻接点中距离$d(v)$最小的点上去,如果邻接点的距离$d(u)=d(v)-1$,则可以推进的流量为$\delta=f(s,v)-f(v,u)$,否则可以推进的流量为$f(s,v)$。如果推进后$f(s,v)$变为$0$,则将节点$v$从高度$h$的桶中移除,并将其加入高度$h+1$的桶中。
3.进行流量推进:从高度最高的桶开始,对于每一个节点$v$,如果$f(s,v)>0$且存在一条从$v$出发的饱和边$(v,u)$,则将流量$\delta=\min(f(s,v),c(v,u)-f(v,u))$从$v$推进到$u$,如果推进后$f(v,u)=c(v,u)$,则将节点$v$从高度$h$的桶中移除,并将其加入高度$h+1$的桶中。
4.重贴标签:如果节点$v$的高度$d(v)$小于$|V|$,且存在一条从$v$出发的非饱和边$(v,u)$,则将节点$v$的高度$d(v)$更新为$d(u)+1$。
5.重复步骤3和4,直至无法再推进流量或者汇点$t$不再可达。
最终的最大流即为源点$s$流出的总流量。