EdmondsKarp算法是Ford-Fulkerson算法的特例，区别在于Ford-Fulkerson算法没有给出残存网络中增广路径的寻找方法，而EdmondsKarp算法使用广度优先搜索寻找增广路径
找到增广路径后沿其递增或递减流，得到更大的流，重复下去直到残存网络不存在增广路径为止
具体见算法导论(第三版):26.2节
算法实现如下(C++)
#include<iostream>#include<vector>#include<deque>usingnamespacestd;#include"graph.h"constintN=6;size_t s=0;size_t t=5;vector<vector<int>>flow_function(N,vector<int>(N,0));//流函数vector<vector<int>>capacity{{0,16,13,0,0,0},{0,0,0,12,0,0},{0,4,0,0,14,0},{0,0,9,0,0,20},{0,0,0,7,0,4},{0,0,0,0,0,0}};//流网络每一条边的容量intmain(){GraphCf(N);//残存网络vector<pair<size_t,size_t>>input{{0,1},{0,2},{1,3},{2,1},{2,4},{3,2},{3,5},{4,3},{4,5}};vector<vector<bool>>adj_matrix(N,vector<bool>(N,false));//流网络的邻接矩阵vector<vector<int>>capacity_f(N,vector<int>(N,0));//残存网络中每条边的容量c(u,v)for(constauto&run:input){adj_matrix[run.first][run.second]=true;}for(size_t i=0;i<N;++i){for(size_t j=0;j<N;++j){if(adj_matrix[i][j]){capacity_f[i][j]=capacity[i][j];if(capacity_f[i][j]!=0){Cf.insertEdge(i,j);}}}}while(true)//广度优先搜索寻找残存网络中的由源点至汇点的增广路径{boolhas_find_path=false;vector<bool>visited(N,false);vector<longlong>pre(N,-1);deque<size_t>work_queue;work_queue.push_back(s);visited[s]=true;while(work_queue.empty()==false){size_t cur=work_queue.front();work_queue.pop_front();for(EdgeNode*run=Cf.getFirstEdge(cur);run!=nullptr;run=Cf.nextEdge(run)){if(visited[run->vertex_id]==false){pre[run->vertex_id]=cur;visited[run->vertex_id]=true;if(run->vertex_id==t){has_find_path=true;break;}work_queue.push_back(run->vertex_id);}}if(has_find_path){break;}}if(has_find_path==false){break;}intCp=-1;size_t run=t;while(pre[run]!=-1){if(Cp==-1||Cp>capacity_f[pre[run]][run]){Cp=capacity_f[pre[run]][run];}run=pre[run];}run=t;while(pre[run]!=-1)//沿增广路径递增流{if(adj_matrix[pre[run]][run]){if(flow_function[pre[run]][run]==0){Cf.insertEdge(run,pre[run]);}flow_function[pre[run]][run]+=Cp;capacity_f[pre[run]][run]-=Cp;if(capacity_f[pre[run]][run]==0){Cf.deleteEdge(pre[run],run);}}else{if(flow_function[run][pre[run]]==capacity[run][pre[run]]){flow_function[run][pre[run]]-=Cp;Cf.insertEdge(run,pre[run]);capacity_f[run][pre[run]]=Cp;}else{flow_function[run][pre[run]]-=Cp;capacity_f[run][pre[run]]+=Cp;}if(flow_function[run][pre[run]]==0){Cf.deleteEdge(pre[run],run);capacity_f[pre[run]][run]=0;}else{capacity_f[pre[run]][run]=flow_function[run][pre[run]];}}run=pre[run];}}cout<<"最大流为"<<endl;for(size_t i=0;i<N;++i)//输出最大流{for(size_t j=0;j<N;j++){if(flow_function[i][j]!=0){cout<<i<<"-"<<j<<":"<<flow_function[i][j]<<endl;}}}return0;}
