线性规划网络流之最短增广路算法
阅读量：3967 次
发布时间：2019-05-24
本文共 3002 字，大约阅读时间需要 10 分钟。
线性规划网络流之最短增广路算法
代码实现
/*最短增广路C++实现参考资料:《趣学算法》陈小玉 人民邮电出版社*/#include #include #include using namespace std;const int MAXNODESIZE=100;//网络最大节点数const int INF=(1<<30)-1;int residualNetwork[MAXNODESIZE][MAXNODESIZE];//残余网络int realFlowNetwork[MAXNODESIZE][MAXNODESIZE];//实流网络int preArray[MAXNODESIZE];//前驱数组bool looked[MAXNODESIZE];//访问数组:记录节点是否已经访问过了int nodeSize,edgeSize;//节点个数与边个数bool bfs(int snode,int enode);//bfs找可增广路int EK(int snode,int enode);//找最短增广路具体算法：对实流网络以及残余网络的操作void print();//输出实流网络int main(void){ int u,v,w; //残余网络初始化为0 memset(residualNetwork,0,sizeof(residualNetwork)); //实流网络初始化为0 memset(realFlowNetwork,0,sizeof(realFlowNetwork)); cout<<"请输入结点个数n与边的数量m: \n"; cin>>nodeSize>>edgeSize; cout<<"请输入两个结点u,v以及u--v的最大容量cap:\n"; for(int i=1;i<=edgeSize;i++){ cin>>u>>v>>w; residualNetwork[u][v]+=w; } cout<<"网络的最大流值为: "< <
Queue; //源点设为已访问 looked[snode]=true; //源点入队列 Queue.push(snode); while(!Queue.empty()){
//如果队列不为空则bfs int now=Queue.front(); Queue.pop(); for(int i=1;i<=nodeSize;i++){
//寻找可增广路 if(!looked[i]&&residualNetwork[now][i]>0){
//now-->i:i没有访问过，且残余网络now-->i还可以增广 looked[i]=true;//结点i设为已访问 preArray[i]=now;//记录结点i的前驱结点 if(i==enode){
//到达汇点，找到一条可增广路 return true; } Queue.push(i);//结点i入队列 } } } return false;//找不到可增广路}//找最短增广路具体算法：对实流网络以及残余网络的操作int EK(int snode,int enode){
int v,w,d,maxflow;//v--->w d:可增广路的可增广量 maxflow:最大流量 maxflow=0;//初始化最大流值 while(bfs(snode,enode)){
//不断更新网络，以达到不再可增广 v=enode; d=INF; while(v!=snode){
//寻找可增广路的可增量:在可增广路中找最小的边权值 w=preArray[v]; if(d>residualNetwork[w][v]){
d=residualNetwork[w][v]; } v=w; } maxflow+=d;//将新加的量加到总流量上 //更新网络 v=enode; while(v!=snode){
w=preArray[v]; residualNetwork[w][v]-=d;//残余网络更新 residualNetwork[v][w]+=d; //实流网络更新 if(realFlowNetwork[v][w]>0){
//正常来说是w--->v增广,如果[v][w]>0则代表实际流向为w<---v,增广量为w--->v的增加 realFlowNetwork[v][w]-=d; }else{
realFlowNetwork[w][v]+=d; } v=w; } } return maxflow;//返回网络最大流量}//输出实流网络void print(){
cout<<"实流网络：\n"; for(int i=1;i<=nodeSize;i++){
cout<<" v"<
测试样例
请输入结点个数n与边的数量m:6 9请输入两个结点u,v以及u--v的最大容量cap:1 2 121 3 102 4 83 2 23 5 134 3 54 6 185 4 65 6 4网络的最大流值为: 18实流网络： v1 v2 v3 v4 v5 v6v1 0 8 10 0 0 0v2 0 0 0 8 0 0v3 0 0 0 0 10 0v4 0 0 0 0 0 14v5 0 0 0 6 0 4v6 0 0 0 0 0 0
转载地址：http://aucki.baihongyu.com/