線性規劃網絡流之最短增廣路算法

代碼實作

/*
最短增廣路C++實作
參考資料:《趣學算法》陳小玉 人民郵電出版社
*/
#include<iostream>
#include<queue>
#include<cstring>
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<<"網絡的最大流值為: "<<EK(1,nodeSize)<<endl;
    print();//輸出實流網絡
    return 0;
}
//bfs找可增廣路
bool bfs(int snode,int enode){
    //初始化前驅數組
    memset(preArray,-1,sizeof(preArray));
    //初始化通路數組
    memset(looked,false,sizeof(looked));
    queue<int>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"<<i;
    }
    cout<<"\n";
    for(int i=1;i<=nodeSize;i++){
        cout<<"v"<<i;
        for(int j=1;j<=nodeSize;j++){
            cout<<"      "<<realFlowNetwork[i][j];
        }
        cout<<"\n";
    }
}
           

測試樣例

請輸入結點個數n與邊的數量m:
6 9
請輸入兩個結點u,v以及u--v的最大容量cap:
1 2 12
1 3 10
2 4 8
3 2 2
3 5 13
4 3 5
4 6 18
5 4 6
5 6 4
網絡的最大流值為: 18
實流網絡：
       v1       v2       v3       v4       v5       v6
v1      0      8      10      0      0      0
v2      0      0      0      8      0      0
v3      0      0      0      0      10      0
v4      0      0      0      0      0      14
v5      0      0      0      6      0      4
v6      0      0      0      0      0      0