Skip to content

求最大流的Relabel-to-Front算法

除了用各种方法在剩余网络中不断找增广路(augmenting)的Ford-Fulkerson系的算法外,还有一种求最大流的算法被称为压入与重标记(Push-Relabel)算法。它的基本操作有:压入,作用于一条边,将边的始点的预流尽可能多的压向终点;重标记,作用于一个点,将它的高度(也就是label)设为所有邻接点的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快,但是缺点是相对难以理解。

Relabel-to-Front使用一个链表保存溢出顶点,用Discharge操作不断使溢出顶点不再溢出。Discharge的操作过程是:若找不到可被压入的临边,则重标记,否则对临边压入,直至点不再溢出。算法的主过程是:首先将源点出发的所有边充满,然后将除源和汇外的所有顶点保存在一个链表里,从链表头开始进行Discharge,如果完成后顶点的高度有所增加,则将这个顶点置于链表的头部,对下一个顶点开始Discharge。

Relabel-to-Front算法的时间复杂度是O(V^3),还有一个叫Highest Label Preflow Push的算法复杂度据说是O(V^2*E^0.5)。我研究了一下HLPP,感觉它和Relabel-to-Front本质上没有区别,因为Relabel-to-Front每次前移的都是高度最高的顶点,所以也相当于每次选择最高的标号进行更新。还有一个感觉也会很好实现的算法是使用队列维护溢出顶点,每次对pop出来的顶点discharge,出现了新的溢出顶点时入队。

Push-Relabel类的算法有一个名为gap heuristic的优化,就是当存在一个整数0<k<V,没有任何顶点满足h[v]=k时,对所有h[v]>k的顶点v做更新,若它小于V+1就置为V+1。不过这个我还没实现,因为现在算法的效率我已经很满意了,以后有空再实现吧。

今天实现的Relabel-to-Front比昨天的距离标号最短增广路又要高效一倍左右。最后感叹一下,网络流真是有趣啊……甚至都想买那本专门讲网络流的书来看看。

示例程序(还是USACO Training Ditch,不过都是自己出数据测的):
ditch(preflow).cpp

5 Comments

  1. 泪洒天堂 wrote:

    您好!我想请教一个问题,在EK算法中,在找到最大流之后,尚可以有办法搜寻到形成这个最大流的一系列子路径,但是在Relabel-to-Front算法中,怎么样才可以搜寻到形成最大流的这些路径呢?告诉我一种方法就行了。谢谢!如果方便,请E-mail一下,chaoweibao@sina.com

    Thursday, June 21, 2007 at 14:33 | Permalink
  2. 你好 wrote:

    大虾,求助啊,最大流最小割1qq79257518,

    Monday, October 8, 2007 at 16:03 | Permalink
  3. radhot wrote:

    push – relabel

    Tuesday, November 13, 2007 at 21:48 | Permalink
  4. radhot wrote:

    求详细源码及测试数据。个人比较感冒JAVA,有JAVA版的更好,谢谢!

    Saturday, November 17, 2007 at 16:55 | Permalink
  5. arena_zp wrote:

    强大,
    谢谢。。
    最大流到目前我都只实现过 Edmonds-Karp 的 V * E^2 的算法。
    呵呵。
    受教受教~~~~

    Wednesday, April 2, 2008 at 10:57 | Permalink

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*