maxflow.cpp

最大流算法,当时学图论的时候写的C++程序,可以用于网络流计算.

//此算法必须指定要求的最大流stream,如果结果无限循环的出现
//一些字或者什么也不出现，则说明该图达不到此流量。
#include<iostream>  
using namespace std;                     
#define max 100
#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];         //原点到各点的最短路径
int D[n];                     //原点到各点的路长(用于Dijkstra法中)
int pt[n];       //原点到各点的路长(用于逐次逼近法中)

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[i]=money[vl][i];            //置初始距离值      
  if((D[i]!=max) && (D[i]!=0)) p[i]=1;
  else p[i]=0;
}

for(i=0;i<n;i++)  s[i]=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]<<"   "<<i+1;    //这里不需要打印
  pre=p[i];
  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][i]-flow[pre-1][i];           //增广路上的最后一条边的长
while(pre!=0)                            //再增广路上算出所能增加流量的最大值
{
     i=pre-1;
  pre=p[pre-1];
  if(min>c[pre-1][i]-flow[pre-1][i])
   min=c[pre-1][i]-flow[pre-1][i];
  if(pre==1)
   pre=0;
}
    if((min+maxflow)>stream)
  min=stream-maxflow;
pre=p[n-1];                    //在增广链上添加流量
i=n-1;
flow[pre-1][i]+=min;
while(pre!=0)
{
  i=pre-1;
  pre=p[pre-1];
  flow[pre-1][i]+=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[i][j]=money[i][j];
for(i=0;i<n;i++)
  for(j=0;j<n;j++)
  {
   if(i<j){
   if(c[i][j]!=max && c[i][j]>flow[i][j])
    money[i][j]=moneypre[i][j];
   if((c[i][j]!=max && c[i][j]==flow[i][j]) || (c[i][j]==max && flow[i][j]==max))
    money[i][j]=max;}
   if(i>j){
   if(  flow[j][i]>0 )
    money[i][j]=-moneypre[j][i];
   if(flow[j][i]==0)
    money[i][j]=max;}
  }
     for(i=0;i<n;i++)
  for(j=0;j<n;j++)
  {
   if(i==j)
    money[i][j]=0;
            if(money[i][j]==-max)
    money[i][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[i];
   for(j=0;j<n;j++)
   {
     
      if(min>(pt[j]+money[j][i]))
       min=pt[j]+money[j][i];
   }
            ptf[i]=min;
  }
   
  for(i=0;i<n;i++)
  { 
    pt[i]=ptf[i];
     if(pf[i]!=pt[i])
    flag=0;     //两次迭代的值不同,继续
  }
}while(flag==0);

j=n-1;  
    for(i=0;i<j;i++)              //找出最短路径走向
if(pt[i]+money[i][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[i]=pt[i];
}
//------------------------------END approach()------------------------------//


void main()
{
cout<<"提示："<<endl;
cout<<"1.修改“#define n  5”可改变问题的规模"<<endl;
cout<<"2.无通路请输入“100”"<<endl;
cout<<endl;
cout<<"输入最大容量:"<<endl;
	for(int a=0;a<n;a++)
		for(int b=0;b<n;b++)
		cin>>c[a][b];
cout<<"输入实际流量:"<<endl;
	for( a=0;a<n;a++)
		for(int b=0;b<n;b++)
		cin>>flow[a][b];
cout<<"输入费用:"<<endl;
	for(a=0;a<n;a++)
		for(int b=0;b<n;b++)
		cin>>money[a][b];
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[i][j]<<"  ";
        cout<<"\n";
}
   cout<<"费用矩阵：\n";
for(i=0;i<n;i++)                    //
{
  for(j=0;j<n;j++)
   cout<<money[i][j]<<"  ";
        cout<<"\n";
}
}