This C++ program implements the Edmonds_Karp Algorithm which is used to compute the maximum flow between the sink and source vertex. It is the same as the Ford-Fulkersson Algorithm except that it uses breadth first search to reduce time complexity.

Here is the source code of the C++ program to display the maximum flow by giving the sink and source nodes as input along with the directed graph. This C++ program is successfully compiled and run on DevCpp, a C++ compiler.The program output is given below.

`/*`

`* C++ Program to Implement The Edmonds-Karp Algorithm`

`*/`

`#include<cstdio>`

`#include<cstdio>`

`#include<queue>`

`#include<cstring>`

`#include<vector>`

`#include<iostream>`

`#include<conio.h>`

using namespace std;

int capacities[10][10];

int flowPassed[10][10];

vector<int> graph[10];

int parentsList[10];

int currentPathCapacity[10];

int bfs(int startNode, int endNode)

`{`

memset(parentsList, -1, sizeof(parentsList));

memset(currentPathCapacity, 0, sizeof(currentPathCapacity));

queue<int> q;

q.push(startNode);

parentsList[startNode] = -2;

currentPathCapacity[startNode] = 999;

while(!q.empty())

`{`

int currentNode = q.front();

q.pop();

for(int i=0; i<graph[currentNode].size(); i++)

`{`

int to = graph[currentNode][i];

if(parentsList[to] == -1)

`{`

if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0)

`{`

parentsList[to] = currentNode;

currentPathCapacity[to] = min(currentPathCapacity[currentNode],

capacities[currentNode][to] - flowPassed[currentNode][to]);

if(to == endNode)

`{`

return currentPathCapacity[endNode];

`}`

q.push(to);

`}`

`}`

`}`

`}`

return 0;

`}`

int edmondsKarp(int startNode, int endNode)

`{`

int maxFlow = 0;

while(true)

`{`

int flow = bfs(startNode, endNode);

if (flow == 0)

`{`

break;

`}`

maxFlow += flow;

int currentNode = endNode;

while(currentNode != startNode)

`{`

int previousNode = parentsList[currentNode];

flowPassed[previousNode][currentNode] += flow;

flowPassed[currentNode][previousNode] -= flow;

currentNode = previousNode;

`}`

`}`

return maxFlow;

`}`

int main()

`{`

int nodesCount, edgesCount;

cout<<"enter the number of nodes and edges\n";

cin>>nodesCount>>edgesCount;

int source, sink;

cout<<"enter the source and sink\n";

cin>>source>>sink;

for(int edge = 0; edge < edgesCount; edge++)

`{`

cout<<"enter the start and end vertex alongwith capacity\n";

int from, to, capacity;

cin>>from>>to>>capacity;

capacities[from][to] = capacity;

graph[from].push_back(to);

graph[to].push_back(from);

`}`

int maxFlow = edmondsKarp(source, sink);

cout<<endl<<endl<<"Max Flow is:"<<maxFlow<<endl;

getch();

`}`

Output enter the number of nodes and edges 6 10 enter the source and sink 0 5 enter the start and end vertex alongwith capacity 0 1 16 enter the start and end vertex alongwith capacity 0 2 13 enter the start and end vertex alongwith capacity 1 2 10 enter the start and end vertex alongwith capacity 2 1 4 enter the start and end vertex alongwith capacity 1 3 12 enter the start and end vertex alongwith capacity 3 2 9 enter the start and end vertex alongwith capacity 2 4 14 enter the start and end vertex alongwith capacity 4 3 7 enter the start and end vertex alongwith capacity 4 5 4 enter the start and end vertex alongwith capacity 3 5 20 Max Flow is:23

**Sanfoundry Global Education & Learning Series – 1000 C++ Programs.**

If you wish to look at all C++ Programming examples, go to C++ Programs.