如何使用预流推进算法求解最大流问题？

2023-08-23 10:00:00 · baa · 乐百管

使用预流推进算法求解最大流问题的步骤如下：给每一个顶点一个标号h(v)，表示该点到t的最短路（在残量网络中）。进行算法过程prepare()，即首先将与s相连的边设为满流，并将这时产生的活动结点

使用预流推进算法求解最大流问题的步骤如下：

给每一个顶点一个标号h(v)，表示该点到t的最短路（在残量网络中）。
进行算法过程prepare()，即首先将与s相连的边设为满流，并将这时产生的活动结点加入队列Q。
重复以下过程直到Q为空： (1). 选出Q的一个活动结点u，并依次判断残量网络G'中每条边(u, v)，若h(u) = h(v) + 1，则顺着这些边推流，直到Q变成非活动结点（不存在多余流量）。 (2). 如果u还是活动结点，则需要对u进行重新标号：h(u) = min{h(v) + 1}，其中边(u,v)存在于G' 中。然后再将u加入队列。
最终得到的结果就是最大流。

如果该算法的Q是标准的FIFO队列，则时间复杂度为(n^2m)，如果是优先队列，并且标号最高的点优先的话，我们就得到了最高标号预流推进算法，其时间复杂度仅为(n^2sqrt(m))，算是比较快的最大流算法了。

_{免责声明：本内容来源于第三方作者授权、网友推荐或互联网整理，旨在为广大用户提供学习与参考之用。所有文本和图片版权归原创网站或作者本人所有，其观点并不代表本站立场。如有任何版权侵犯或转载不当之情况，请您通过400-62-96871或关注我们的公众号与我们取得联系，我们将尽快进行相关处理与修改。感谢您的理解与支持！}