Edmonds Karp Algorithm in C++

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.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Find Maximum Number of Edge Disjoint Paths

» Next - C++ Program to Implement Traveling Salesman Problem using Nearest Neighbour Algorithm

Related Posts:

Recommended Articles: