最短增益路径法求解最大流问题

深 圳 大 学 实 验 报 告

课程名称： 算法分析与复杂性理论

实验项目名称： 实验五 最短增益路径法求解最大流问题

学院： 计算机与软件学院

专业： 软件工程

指导教师：

报告人： 学号： 班级：

实验时间： 2015-10-22

实验报告提交时间： 2015-11-30

教务部制

一．实验目的

1. 掌握最短增益路径法思想。

2. 学会最大流问题求解方法。

二．实验步骤与结果

实验总体思路：

通过capacity[][]二维数组存储对应边的容量，并用两个一维数组分别保存边的剩余流量和路径上当前节点的前驱。用C++中的queue类实现队列的相关操作，进而实现BFS算法。输入有向图中边的个数和顶点个数之后，通过一个for循环获取对应边的始点、终点和容量，并将这些数据保存到capacity[][]数组中。程序设计中将源点设为1，将汇点设为最后一个顶点。（代码和结果如下图所示）。

各排序算法的实现及实验结果：

1、EK算法

代码1：

bool Edmonds_Karp(int src,int des,int n){

int v,i;

for(i=0;i

front=rear=0; //初始化

que[rear++]=src;

visit[src]=true;

while(front!=rear){ //将源点进队后开始广搜的操作

v=que[front++];

for(i=0;i

if(!visit[i]&&c[v][i]){ //只有残留容量大于0时才存在边

que[rear++]=i;

visit[i]=true;

pre[i]=v;

if(i==des)return true; //如果已经到达汇点，说明存在增广路径返回true

}

}

}

return false;

}

代码2：

int BFS(){
    int i,j,k,v,u;
    memset(pre,-1,sizeof(pre));
    for(i=1;i<=n;++i)flow[i]=max_int;
    queueque;
    pre[start]=0;
    que.push(start);
    while(!que.empty()){
        v=que.front();
        que.pop();
        for(i=1;i<=n;++i){
            u=i;
            if(u==start||pre[u]!=-1||map[v][u]==0)continue;
            pre[u]=v;
            flow[u]=MIN(flow[v],map[v][u]);
            que.push(u);
        }
    }
    if(flow[end]==max_int)return -1;
    return flow[end];
}

算法说明： 每次用BFS找一条最短的增广路径，然后沿着这条路径修改流量值（实际修改的是残量网络的边权）。当没有增广路时，算法停止，此时的流就是最大。

实验结果：

（注：由于是根据前驱来找路径的，故输出路径为（终点，始点，容量）。）

第1次迭代：

(6,3,4)、(3,2,4)、(2,1,4)

第2次迭代：

(6,5,2)、(5,2,2)、(2,1,2)

第3次迭代：

(6,5,2)、(5,4,2)、(4,1,2)

第4次迭代：

(6,3,2)、(3,2,2)、(2,1,2)

总结：

根据通信网络中边的个数和顶点个数n =|V| ,m = |E|, 每进行一次增广BFS搜索算法，效率为O(m),而在最坏的情况下需要（n-2）增广（即除源点和汇点外其他点都没有连通，所有点都只和s与t连通）。所以,最短增益路径法的时间复杂度为O(m*n)，这在稀疏图中效率比较高。

四．实验心得

解决一个问题最重要的是理解它的解题算法，只有掌握解题的思路，才能使得程序的实现事半功倍。Edmonds-Karp算法实际上就是采用广度优先搜索来实现对增广路径的计算，这种算法思想在很多方面都有应用。

实验过程难免会遇到问题，掌握好的调试技巧能够快速查找出问题的所在，并通过排查，逐一改正程序中存在的问题，不管用什么编译器，都要学会设置适当的断点。遇到不懂的地方要多查看相关的书籍或者在网上查找资料，这样才能真正学到东西。

附件：源码

#include

#include

#include

using namespace std;

#define arraysize 201

int maxData = 0x7fffffff;

int capacity[arraysize][arraysize]; //记录残留网络的容量

int flow[arraysize]; //标记从源点到当前节点实际还剩多少流量可用

int pre[arraysize]; //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中

int n,m;

queue myqueue;

int BFS(int src,int des){

int i,j;

while(!myqueue.empty()) //队列清空

myqueue.pop();

for(i=1;i //初始都为未标记

pre[i]=-1;

}

pre[src]=0; //源点的前驱为0

flow[src]= maxData;

myqueue.push(src); //源点进队列

while(!myqueue.empty()){

int index = myqueue.front(); //返回myqueue内的第一个元素

myqueue.pop();

if(index == des)//找到了增广路径

break;

for(i=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;

int s = 1;

while((increasement=BFS(src,des))!=-1){

int k = des; //利用前驱寻找路径

cout<<"第"<次迭代：";

while(k!=src)

{

int last = pre[k];

cout<<"("<

capacity[last][k] -= increasement; //改变正向边的容量

capacity[k][last] += increasement; //改变反向边的容量

k = last;

}

cout<<"\t路径的最大流值："<

sumflow += increasement;

s++;

}

return sumflow;

}

int main()

{

int i,j;

int start,end,ci; //边的起点、终点和容量

cout<<"输入边的个数和顶点个数：";

while(cin>>n>>m)

{

memset(capacity,0,sizeof(capacity));

memset(flow,0,sizeof(flow));

for(i=0;i

{

cin>>start>>end>>ci;

if(start == end) //考虑起点终点相同的情况

continue;

capacity[start][end] +=ci; //此处注意可能出现多条同一起点终点的情况

}

cout<最大流的值是:"<

}

return 0;

}

本文来源：https://www.2haoxitong.net/k/doc/a8d5c871c1c708a1294a445c.html