文档章节

网络流—最大流(Edmond-Karp算法)

吟啸_徐行
 吟啸_徐行
发布于 2013/07/13 21:34
字数 1528
阅读 162
收藏 1
点赞 0
评论 1

首先要先清楚最大流的含义,就是说从源点到经过的所有路径的最终到达汇点的所有流量和


EK算法的核心
反复寻找源点s到汇点t之间的增广路径,若有,找出增广路径上每一段[容量-流量]的最小值delta,若无,则结束。
在寻找增广路径时,可以用BFS来找,并且更新残留网络的值(涉及到反向边)。
而找到delta后,则使最大流值加上delta,更新为当前的最大流值。

这么一个图,求源点1,到汇点3的最大流

由于我是通过模版真正理解ek的含义,所以先上代码,通过分析代码,来详细叙述ek算法

View Code 
 #include <iostream>
 #include <queue>
 #include<string.h>
 using namespace std;
 #define arraysize 201
 int maxData = 0x7fffffff;
 int capacity[arraysize][arraysize]; //记录残留网络的容量
 int flow[arraysize];                //标记从源点到当前节点实际还剩多少流量可用
 int pre[arraysize];                 //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中
 int n,m;
 queue<int> myqueue;
 int BFS(int src,int des)
 {
     int i,j;
     while(!myqueue.empty())       //队列清空
         myqueue.pop();
     for(i=1;i<m+1;++i)
     {
         pre[i]=-1;
     }
     pre[src]=0;
     flow[src]= maxData;
     myqueue.push(src);
     while(!myqueue.empty())
     {
         int index = myqueue.front();
         myqueue.pop();
         if(index == des)            //找到了增广路径
             break;
         for(i=1;i<m+1;++i)
         {
             if(i!=src && capacity[index][i]>0 && pre[i]==-1)
             {
                  pre[i] = index; //记录前驱
                  flow[i] = min(capacity[index][i],flow[index]);   //关键:迭代的找到增量
                  myqueue.push(i);
             }
         }
     }
     if(pre[des]==-1)      //残留图中不再存在增广路径
         return -1;
     else
         return flow[des];
 }
 int maxFlow(int src,int des)
 {
     int increasement= 0;
     int sumflow = 0;
     while((increasement=BFS(src,des))!=-1)
     {
          int k = des;          //利用前驱寻找路径
          while(k!=src)
          {
               int last = pre[k];
               capacity[last][k] -= increasement; //改变正向边的容量
               capacity[k][last] += increasement; //改变反向边的容量
               k = last;
          }
          sumflow += increasement;
     }
     return sumflow;
 }
 int main()
 {
     int i,j;
     int start,end,ci;
     while(cin>>n>>m)
     {
         memset(capacity,0,sizeof(capacity));
         memset(flow,0,sizeof(flow));
         for(i=0;i<n;++i)
         {
             cin>>start>>end>>ci;
             if(start == end)               //考虑起点终点相同的情况
                continue;
             capacity[start][end] +=ci;     //此处注意可能出现多条同一起点终点的情况
         }
         cout<<maxFlow(1,m)<<endl;
     }
     return 0;
 }

显而易见capacity存变的流量,进行ek求解

对于BFS找增广路:

1.         flow[1]=INF,pre[1]=0;

        源点1进队列,开始找增广路,capacity[1][2]=40>0,则flow[2]=min(flow[1],40)=40;

        capacity[1][4]=20>0,则flow[4]=min(flow[1],20)=20;

        capacity[2][3]=30>0,则flow[3]=min(folw[2]=40,30)=30;

        capacity[2][4]=30,但是pre[4]=1(已经在capacity[1][4]这遍历过4号点了)

        capacity[3][4].....

        当index=4(汇点),结束增广路的寻找

        传递回increasement(该路径的流),利用前驱pre寻找路径

路径也自然变成了这样:

2.flow[1]=INF,pre[1]=0;

 源点1进队列,开始找增广路,capacity[1][2]=40>0,则flow[2]=min(flow[1],40)=40;

        capacity[1][4]=0!>0,跳过

        capacity[2][3]=30>0,则flow[3]=min(folw[2]=40,30)=30;

        capacity[2][4]=30,pre[4]=2,则flow[2][4]=min(flow[2]=40,20)=20;

        capacity[3][4].....

        当index=4(汇点),结束增广路的寻找

        传递回increasement(该路径的流),利用前驱pre寻找路径

 图也被改成

  

接下来同理

这就是最终完成的图,最终sumflow=20+20+10=50(这个就是最大流的值)

 

 

PS,为什么要有反向边呢?

 

我们第一次找到了1-2-3-4这条增广路,这条路上的delta值显然是1。于是我们修改后得到了下面这个流。(图中的数字是容量)

 

这时候(1,2)和(3,4)边上的流量都等于容量了,我们再也找不到其他的增广路了,当前的流量是1。

但这个答案明显不是最大流,因为我们可以同时走1-2-4和1-3-4,这样可以得到流量为2的流。

那么我们刚刚的算法问题在哪里呢?问题就在于我们没有给程序一个”后悔”的机会,应该有一个不走(2-3-4)而改走(2-4)的机制。那么如何解决这个问题呢?回溯搜索吗?那么我们的效率就上升到指数级了。

而这个算法神奇的利用了一个叫做反向边的概念来解决这个问题。即每条边(I,j)都有一条反向边(j,i),反向边也同样有它的容量。

我们直接来看它是如何解决的:

在第一次找到增广路之后,在把路上每一段的容量减少delta的同时,也把每一段上的反方向的容量增加delta。即在Dec(c[x,y],delta)的同时,inc(c[y,x],delta)

我们来看刚才的例子,在找到1-2-3-4这条增广路之后,把容量修改成如下

这时再找增广路的时候,就会找到1-3-2-4这条可增广量,即delta值为1的可增广路。将这条路增广之后,得到了最大流2。

 

那么,这么做为什么会是对的呢?我来通俗的解释一下吧。

事实上,当我们第二次的增广路走3-2这条反向边的时候,就相当于把2-3这条正向边已经是用了的流量给”退”了回去,不走2-3这条路,而改走从2点出发的其他的路也就是2-4。(有人问如果这里没有2-4怎么办,这时假如没有2-4这条路的话,最终这条增广路也不会存在,因为他根本不能走到汇点)同时本来在3-4上的流量由1-3-4这条路来”接管”。而最终2-3这条路正向流量1,反向流量1,等于没有流量。

这就是这个算法的精华部分,利用反向边,使程序有了一个后悔和改正的机会。而这个算法和我刚才给出的代码相比只多了一句话而已。

至此,最大流Edmond-Karp算法介绍完毕。


本文转载自:http://www.wutianqi.com/?p=3107

共有 人打赏支持
吟啸_徐行
粉丝 18
博文 108
码字总数 15604
作品 0
深圳
程序员
加载中

评论(1)

吟啸_徐行
吟啸_徐行
精彩啊
网络最大流

网络最大流 例题: 如果网络结构复杂,就得靠算法算出结果。 这里需要注意容量和流量的区别。其中f(u,v)的范围需要额外注意,是 0<= f(u,v) <= c(u,v),不会出现所谓的负流量。 网络流的三个...

evsqiezi ⋅ 2017/12/02 ⋅ 0

Ford-Fulkerson 方法——最大流问题

最大流&&最小费用最大流&&最大二分匹配 Python 源码:https://github.com/edisonleolhl/DataStructure-Algorithm/blob/master/Graph/MaxFlow 最大流问题 比喻:有一个自来水管道运输系统,起...

廖少少 ⋅ 2017/09/08 ⋅ 0

计算机科学中最重要的32个算法

转载:http://www.infoq.com/cn/news/2012/08/32-most-important-algorithms 奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutschan博士在自......

Nov_Eleven ⋅ 2013/06/23 ⋅ 0

计算机科学中最重要的32个算法

奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章,提到他做了一个调查,参与者大多数是计算机科学家...

xrzs ⋅ 2012/09/05 ⋅ 0

转:32种常用算法

奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章,提到他做了一个调查,参与者大多数是计算机科学家...

沐春风23 ⋅ 2013/06/24 ⋅ 3

数据结构学习笔记(01背包问题/图问题)

01背包问题:在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。求如何安排能带走最多价值的物品? 动态规划解决背包问题: 设f(i,W)表...

duanbowen ⋅ 2017/06/01 ⋅ 0

用Ford和Fulkerson的增广路径算法,解决网络中的最大流(flow)以及其衍生问题。

管道网络中每条边的最大通过能力(容量)是有限的,实际流量不超过容量。 最大流问题(maximum flow problem),一种组合最优化问题,就是要讨论如何充分利用装置的能力,使得运输的流量最大,...

linuxer ⋅ 2017/11/11 ⋅ 0

数据结构及其变化

集合 散列表 定义: 散列表:通过将元素映射到该表中的某一位置,来提高访问速度 装填因子:元素的个数/表的长度 碰撞: 多个关键字映射到同一位置的现象 碰撞检测方案:直接寻址法和链接法 ...

158114527090 ⋅ 2017/06/20 ⋅ 0

搞定编程大赛必知哪10个算法?

再没有比算法更让人头疼的东西了吧! 前两天参加了一个编程大赛http://www.ijiami.cn/newsInfo?id=519&v=2,有感于算法,所以整理了这篇关于编程竞赛的10个算法。 动态规划(DP)似乎占据了大...

小开2014 ⋅ 2014/10/22 ⋅ 6

优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆 ⋅ 2011/12/03 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周日乱弹 —— 这么好的姑娘都不要了啊

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @TigaPile :分享曾惜的单曲《讲真的》 《讲真的》- 曾惜 手机党少年们想听歌,请使劲儿戳(这里) @首席搬砖工程师 :怎样约女孩子出来吃饭,...

小小编辑 ⋅ 13分钟前 ⋅ 1

Jenkins实践3 之脚本

#!/bin/sh# export PROJ_PATH=项目路径# export TOMCAT_PATH=tomcat路径killTomcat(){pid=`ps -ef | grep tomcat | grep java|awk '{print $2}'`echo "tom...

晨猫 ⋅ 今天 ⋅ 0

Spring Bean的生命周期

前言 Spring Bean 的生命周期在整个 Spring 中占有很重要的位置,掌握这些可以加深对 Spring 的理解。 首先看下生命周期图: 再谈生命周期之前有一点需要先明确: Spring 只帮我们管理单例模...

素雷 ⋅ 今天 ⋅ 0

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 今天 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部