[原创]关于最小费用最大流的一个Ｃ算法

shenhui · 发表于 2005-7-17 22:40:00

<

>//2005.4.12 //written by shenhui //此算法必须指定要求的最大流stream,如果结果无限循环的出现 //一些字或者什么也不出现，则说明该图达不到此流量。 #include "iostream.h" #define max 10000 #define n 5 //根据不同问题可修改大小 #define stream 10 //根据不同问题可修改 //最大容量矩阵 int c[n][n]={{0,10,8,max,max},{max,0,max,2,7},{max,5,0,10,max},{max,max,max,0,4},{max,max,max,max,0}}; //实际流量矩阵 int flow[n][n]={{0,0,0,max,max},{max,0,max,0,0},{max,0,0,0,max},{max,max,max,0,0},{max,max,max,max,0}}; //费用矩阵 int money[n][n]={{0,4,1,max,max},{max,0,max,6,1},{max,2,0,3,max},{max,max,max,0,2},{max,max,max,max,0}}; //增广链向量 int p[n]={0,0,0,0,0}; //原点到各点的最短路径 int D[n]; //原点到各点的路长(用于Dijkstra法中) int pt[n]={0,0,0,0,0}; //原点到各点的路长(用于逐次逼近法中)
<

>int maxflow; //设置最大流量

<

> //----------------------------计算Vs--Vt最短路径模块---------------------------------------------//
void Dijkstra() //求源点V0到其余顶点的最短路径及其长度;得到一条增广链 { int s[n]; //D[n]最后保存各点的最短路径长度 int i,j,k,vl,pre; int min; int inf=20000; vl=0; //求V0到Vn的增广链 for(i=0;i<n;i++) { D=money[vl]; //置初始距离值 if((D!=max) && (D!=0)) p=1; else p=0; }
 for(i=0;i<n;i++) s=0; s[vl]=1; D[vl]=0; for(i=0;i<n;i++) { min=inf; for(j=0;j<n;j++) if((!s[j]) && (D[j]<min)) { min=D[j]; k=j; } s[k]=1; if(min==max) break; for(j=0;j<n;j++) if((!s[j]) && (D[j]>D[k]+money[k][j])) { D[j]=D[k]+money[k][j]; p[j]=k+1; } } //此时所有顶点都已扩充到红点集S中 cout<<"Vs到Vt的最短路径为(长和径):\n"; for(i=0;i<n;i++) { if(i=n-1){ cout<<D<<" "<<i+1; //这里不需要打印 pre=p; while (pre!=0) { cout<<"<-- "<<pre; //这里不需要打印 pre=p[pre-1]; //p[]中保存的路径的顶点标号从1开始，不是0； } cout<<"\n";} } } //-----------------------------------END Dijkstra()-----------------------------------------//

 //------------------用最大流算法的方法调整实际流量矩阵flow[][]，以扩充其流量----------------// void modify() { int i,min; int pre; if(D[n-1]==max) { cout<<"不存在增广链"; return; }
 pre=p[n-1]; i=n-1; min=c[pre-1]-flow[pre-1]; //增广路上的最后一条边的长 while(pre!=0) //再增广路上算出所能增加流量的最大值 { i=pre-1; pre=p[pre-1]; if(min>c[pre-1]-flow[pre-1]) min=c[pre-1]-flow[pre-1]; if(pre==1) pre=0; } if((min+maxflow)>stream) min=stream-maxflow; pre=p[n-1]; //在增广链上添加流量 i=n-1; flow[pre-1]+=min; while(pre!=0) { i=pre-1; pre=p[pre-1]; flow[pre-1]+=min; if(pre==1) pre=0; } } //----------------------------------END modify()----------------------------------//

 //--------------------------------调整费用矩阵money[][]-----------------------------// void modifymoney() { int i,j; int moneypre[n][n]; for(i=0;i<n;i++) for(j=0;j<n;j++) moneypre[j]=money[j]; for(i=0;i<n;i++) for(j=0;j<n;j++) { if(i<j){ if(c[j]!=max && c[j]>flow[j]) money[j]=moneypre[j]; if((c[j]!=max && c[j]==flow[j]) || (c[j]==max && flow[j]==max)) money[j]=max;} if(i>j){ if( flow[j]>0 ) money[j]=-moneypre[j]; if(flow[j]==0) money[j]=max;} } for(i=0;i<n;i++) for(j=0;j<n;j++) { if(i==j) money[j]=0; if(money[j]==-max) money[j]=max; } } //----------------------------------END modifymoney()----------------------------------//

//----------------------------采用逐次逼近法得到一条增广链----------------------------// void approach() { int pf[n],ptf[n]={0,0,0,0,0}; //当N变动时，0的个数应与N一致 int min=max; int i,j,flag; for(j=0;j<n;j++) pt[j]=money[0][j]; //直接距离做初始解 do{ flag=1; for(j=0;j<n;j++) pf[j]=pt[j]; //将上一次得到的路径迭代结果保存入pf[] for(i=0;i<n;i++) { min=pt; for(j=0;j<n;j++) { if(min>(pt[j]+money[j])) min=pt[j]+money[j]; } ptf=min; } for(i=0;i<n;i++) { pt=ptf; if(pf!=pt) flag=0; //两次迭代的值不同,继续 } }while(flag==0);
 j=n-1; for(i=0;i<j;i++) //找出最短路径走向 if(pt+money[j]==pt[j]) { p[j]=i+1; //p[j]中的下标从1开始 if(p[j]==1) break; j=i; i=-1; } for(i=0;i<n;i++) D=pt; } //------------------------------END approach()------------------------------//

 void main() { int i,j; Dijkstra(); while( 1 ) { modify(); //调整流量矩阵 maxflow=0; for(j=0;j<n;j++) { if(flow[0][j]!=max) maxflow+=flow[0][j]; } if(maxflow==stream) break; modifymoney(); approach(); //采用逐次逼近法得到一条增广链 } cout<<"流量矩阵：\n"; for(i=0;i<n;i++) // { for(j=0;j<n;j++) cout<<flow[j]<<" "; cout<<"\n"; } cout<<"费用矩阵：\n"; for(i=0;i<n;i++) // { for(j=0;j<n;j++) cout<<money[j]<<" "; cout<<"\n"; } }

dormouse_buaa · 发表于 2005-7-20 03:15:36

不错，不错。辛苦了[em17]

myself · 发表于 2005-8-26 03:58:11

<

>楼主辛苦拉

		自动登录	找回密码
密码			注-册-帐-号