关于最大流的EdmondsKarp算法详解

简介: 最近大三学生让我去讲课,我就恶补了最大流算法,笔者认为最重要的是让学弟学妹们入门,知道算法怎么来的?为什么是这样?理解的话提出自己的改进,然后再看看Dinic、SAP和ISAP算法….. 一、概念引入       首先要先清楚最大流的含义,就是说从源点到经过的所有路径的最终到达汇点的所有流量和。

      最近大三学生让我去讲课,我就恶补了最大流算法,笔者认为最重要的是让学弟学妹们入门,知道算法怎么来的?为什么是这样?理解的话提出自己的改进,然后再看看Dinic、SAP和ISAP算法…..

一、概念引入

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

      流网络G=(V,E)是一个有向图,其中每条边(u,v)∈E均有一个非负容量c(u,v)>=0。如果(u,v)不属于E,则假定c(u,v)=0。流网络中有两个特别的顶点:源点s和汇点t。下图展示了一个流网络的实例(其中斜线左边的数字表示实际边上的流,右边的数字表示边的最大容量):

                      image

二、基础知识准备

      对一个流网络G=(V,E),其容量函数为c,源点和汇点分别为s和t。G的流f满足下列三个性质:
      容量限制:对所有的u,v∈V,要求f(u,v)<=c(u,v)。
      反对称性:对所有的u,v∈V,要求f(u,v)=-f(v,u)。
      流守恒性:对所有u∈V-{s,t},要求∑f(u,v)=0 (v∈V)。

      容量限制说明了从一个顶点到另一个顶点的网络流不能超过设定的容量,就好像是一个管道只能传输一定容量的水,而不可能超过管道体积的限制;反对称性说明了从顶点u到顶点v的流是其反向流求负所得,就好像是当参考方向固定后,站在不同的方向看,速度一正一负;而流守恒性说明了从非源点或非汇点的顶点出发的点网络流之和为0,这有点类似于基尔霍夫电流定律,且不管什么是基尔霍夫电流定律,通俗的讲就是进入一个顶点的流量等于从该顶点出去的流量,如果这个等式不成立,必定会在该顶点出现聚集或是枯竭的情况,而这种情况是不应该出现流网络中的,所以一般的最大流问题就是在不违背上述原则的基础上求出从源点s到汇点t的最大的流量值,显然这个流量值应该定义为从源点出发的总流量或是最后聚集到t的总流量,即流f的值定义为|f|=∑f(s,v) (v∈V)。

      在求解最大流的问题前,必须对三个概念有所了解:残留网络,增广路径和割。下面先给出这三个概念的基本内容。
      a.在给定的流网络G=(V,E)中,设f为G中的一个流,并考察一对顶点u,v∈V,在不超过容量c(u,v)的条件下,从u到v之间可以压入的额外网络流量,就是(u,v)的残留容量,就好像某一个管道的水还没有超过管道的上限,那么就这条管道而言,就一定还可以注入更多的水。残留容量的定义为:cf(u,v)=c(u,v)-f(u,v)。而由所有属于G的边的残留容量所构成的带权有向图就是G的残留网络。下图就是上面的流网络所对应的残留网络:

                                  image

      残留网络中的边既可以是E中边,也可以是它们的反向边。只有当两条边(u,v)和(v,u)中,至少有一条边出现在初始网络中时,边(u,v)才会出现在残留网络中。下面是一个有关残留网络的定理,若f是G中的一个流,Gf是由G导出的残留网络,f'是Gf中的一个流,则f+f'是G中一个流,且其值|f+f'|=|f|+|f'|。证明时只要证明f+f'这个流在G中满足之前所讲述的三个原则即可。在这里只给出理解性的证明,可以想象如果在一个管道中流动的水的总流量为f,而在该管道剩余的流量中存在一个流f'可以满足不会超过管道剩余流量的最大限,那么将f和f'合并后,也必定不会超过管道的总流量,而合并后的总流量值也一定是|f|+|f'|。

      b.增广路径p为残留网络Gf中从s到t的一条简单路径。根据残留网络的定义,在不违反容量限制的条件下,G中所对应的增广路径上的每条边(u,v)可以容纳从u到v的某额外正网络流。而能够在这条路径上的网络流的最大值一定是p中边的残留容量的最小值。这还是比较好理解的,因为如果p上的流大于某条边上的残留容量,必定会在这条边上出现流聚集的情况。所以我们将最大量为p的残留网络定义为:cf(p)=min{cf(u,v) | (u,v)在p上}。而结合之前在残留网络中定理,由于p一定是残留网络中从s到t的一条路径,且|f'|=cf(p),所以若已知G中的流f,则有|f|+|cf(p)|>|f|且|f|+|cf(p)|不会超过容量限制。

      c.流网络G(V,E)的割(S,T)将V划分成为S和T=V-S两部分,使得s∈S,t∈T。如果f是一个流,则穿过割(S,T)的净流被定义为f(S,T)=∑f(x,y) (x∈S,y∈T),割(S,T)的容量为c(S,T)。一个网络的最小割就是网络中所有割中具有最小容量的割。设f为G中的一个流,且(S,T)是G中的一个割,则通过割(S,T)的净流f(S,T)=|f|。因为f(S,T)=f(S,V)-f(S,S)=f(S,V)=f(s,V)+f(S-s,V)=f(s,V)=|f|(这里的公式根据f(X,Y)=∑f(x,y) (x∈X,y∈Y)的定义,以及前面的三个限制应该还是可以推出来的,这里就不细讲了)。有了上面这个定理,我们可以知道当把流不断增大时,流f的值|f|不断的接近最小割的容量直到相等,如果这时可以再增大流f,则f必定会超过某个最小的割得容量,则就会存在一个f(S,T)<=c(S,T)<|f|,显然根据上面的定理这是不可能。所以最大流必定不超过网络最小割的容量。

      综合上面所讲,有一个很重要的定理:最大流最小割定理

如果f是具有源s和汇点t的流网络G=(V,E)中的一个流,则下列条件是等价的:
      1) f是G中一个最大流。
      2) 残留网络Gf不包含增广路径。
      3) 对G的某个割(S,T),有|f|=c(S,T)。

三、代码实现

      不想写一个Java版本的了。remnant 残量。

#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;
}

  用的时候自己修改一下。

bool EK_Bfs (int start, int end)//广搜用于找增广路;
{
            bool flag[Maxn];//标记数组
            memset (flag, false, sizeof(flag));
            memset (p, -1, sizeof(p));
            flag[start] = true;
            queue t;
            t.push(start);
            while (!t.empty())
            {
                  int top = t.front();
                  if (top == end)return true;// 此时找到增广路
                  t.pop();
                  for (int i=1; i<=n; i++)
                  {
                      if (map[top][i] && !flag[i])
                      {
                         flag[i] = true;
                         t.push(i);
                         p[i] = top;// 记录前驱(很关键)
                      }
                  }
            }
            return false;
}
int E_K (int start,int end)
{
        int u,max = 0,mn;//max用来初始化最大流为0;
        while (EK_Bfs(start,end))//当增广成功时
        {
              mn = 100000;
              u = end;
              while (p[u] != -1)//寻找”瓶颈“边,并且记录容量;
              {
                    mn = min (mn, map[p[u]][u]);
                    u = p[u];
              }
              max += mn;//累加边的最大流; 
              u = end;
              while (p[u] != -1)//修改路径上的边容量;
              {
                    map[p[u]][u] -= mn;
                    map[u][p[u]] += mn;
                    u = p[u];
              }
        }
        return max;
}
目录
相关文章
|
算法
计算机基础问题,最大流问题获突破性进展:新算法「快得离谱」
计算机基础问题,最大流问题获突破性进展:新算法「快得离谱」
|
算法
GraphCuts算法解析,Graphcuts算法求最大流,最小割实例
   图割论文大合集下载: http://download.csdn.net/detail/wangyaninglm/8292305   代码: /* graph.h */ /* Vladimir Kolmogorov (vnk@cs.
1198 0
|
机器学习/深度学习 算法 JavaScript
【算法导论】最大流算法
最大流问题就是在容量容许的条件下,从源点到汇点所能通过的最大流量。 1 流网络        网络流G=(v, E)是一个有向图,其中每条边(u, v)均有一个非负的容量值,记为c(u, v) ≧ 0。
1158 0
|
2天前
|
传感器 算法 C语言
基于无线传感器网络的节点分簇算法matlab仿真
该程序对传感器网络进行分簇,考虑节点能量状态、拓扑位置及孤立节点等因素。相较于LEACH算法,本程序评估网络持续时间、节点死亡趋势及能量消耗。使用MATLAB 2022a版本运行,展示了节点能量管理优化及网络生命周期延长的效果。通过簇头管理和数据融合,实现了能量高效和网络可扩展性。
|
29天前
|
算法 BI Serverless
基于鱼群算法的散热片形状优化matlab仿真
本研究利用浴盆曲线模拟空隙外形,并通过鱼群算法(FSA)优化浴盆曲线参数,以获得最佳孔隙度值及对应的R值。FSA通过模拟鱼群的聚群、避障和觅食行为,实现高效全局搜索。具体步骤包括初始化鱼群、计算适应度值、更新位置及判断终止条件。最终确定散热片的最佳形状参数。仿真结果显示该方法能显著提高优化效率。相关代码使用MATLAB 2022a实现。
|
29天前
|
算法 数据可视化
基于SSA奇异谱分析算法的时间序列趋势线提取matlab仿真
奇异谱分析(SSA)是一种基于奇异值分解(SVD)和轨迹矩阵的非线性、非参数时间序列分析方法,适用于提取趋势、周期性和噪声成分。本项目使用MATLAB 2022a版本实现从强干扰序列中提取趋势线,并通过可视化展示了原时间序列与提取的趋势分量。代码实现了滑动窗口下的奇异值分解和分组重构,适用于非线性和非平稳时间序列分析。此方法在气候变化、金融市场和生物医学信号处理等领域有广泛应用。
|
1月前
|
资源调度 算法
基于迭代扩展卡尔曼滤波算法的倒立摆控制系统matlab仿真
本课题研究基于迭代扩展卡尔曼滤波算法的倒立摆控制系统,并对比UKF、EKF、迭代UKF和迭代EKF的控制效果。倒立摆作为典型的非线性系统,适用于评估不同滤波方法的性能。UKF采用无迹变换逼近非线性函数,避免了EKF中的截断误差;EKF则通过泰勒级数展开近似非线性函数;迭代EKF和迭代UKF通过多次迭代提高状态估计精度。系统使用MATLAB 2022a进行仿真和分析,结果显示UKF和迭代UKF在非线性强的系统中表现更佳,但计算复杂度较高;EKF和迭代EKF则更适合维数较高或计算受限的场景。
下一篇
无影云桌面