C++ Program to Implement Edmonds Karp Algorithm

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.

  1. /*
  2.  * C++ Program to Implement The Edmonds-Karp Algorithm
  3.  */
  4. #include<cstdio>
  5. #include<cstdio>
  6. #include<queue>
  7. #include<cstring>
  8. #include<vector>
  9. #include<iostream>
  10. #include<conio.h>
  11.  
  12. using namespace std; 
  13.  
  14. int capacities[10][10];
  15. int flowPassed[10][10];
  16. vector<int> graph[10];
  17. int parentsList[10];       
  18. int currentPathCapacity[10];  
  19.  
  20. int bfs(int startNode, int endNode)
  21. {
  22.     memset(parentsList, -1, sizeof(parentsList));
  23.     memset(currentPathCapacity, 0, sizeof(currentPathCapacity));
  24.  
  25.     queue<int> q;
  26.     q.push(startNode);
  27.  
  28.     parentsList[startNode] = -2;
  29.     currentPathCapacity[startNode] = 999;
  30.  
  31.     while(!q.empty())
  32.     {
  33.         int currentNode = q.front();
  34.         q.pop();
  35.  
  36.         for(int i=0; i<graph[currentNode].size(); i++)
  37.         {
  38.             int to = graph[currentNode][i];
  39.             if(parentsList[to] == -1)
  40.             {
  41.                 if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0)
  42.                 {
  43.                     parentsList[to] = currentNode;
  44.                     currentPathCapacity[to] = min(currentPathCapacity[currentNode], 
  45.                     capacities[currentNode][to] - flowPassed[currentNode][to]);
  46.                     if(to == endNode)
  47.                     {
  48.                         return currentPathCapacity[endNode];
  49.                     }
  50.                     q.push(to);
  51.                 }
  52.             }
  53.         }
  54.     }
  55.     return 0;
  56. }
  57.  
  58. int edmondsKarp(int startNode, int endNode)
  59. {
  60.     int maxFlow = 0;
  61.       while(true)
  62.     {
  63.         int flow = bfs(startNode, endNode);
  64.         if (flow == 0) 
  65.         {
  66.             break;
  67.         }
  68.         maxFlow += flow;
  69.         int currentNode = endNode;
  70.         while(currentNode != startNode)
  71.         {
  72.             int previousNode = parentsList[currentNode];
  73.             flowPassed[previousNode][currentNode] += flow;
  74.             flowPassed[currentNode][previousNode] -= flow;
  75.             currentNode = previousNode;
  76.         }
  77.     }
  78.     return maxFlow;
  79. }
  80. int main()
  81. {
  82.     int nodesCount, edgesCount;
  83.     cout<<"enter the number of nodes and edges\n";
  84.     cin>>nodesCount>>edgesCount;
  85.  
  86.     int source, sink;
  87.     cout<<"enter the source and sink\n";
  88.     cin>>source>>sink;
  89.  
  90.     for(int edge = 0; edge < edgesCount; edge++)
  91.     {
  92.         cout<<"enter the start and end vertex alongwith capacity\n";
  93.         int from, to, capacity;
  94.         cin>>from>>to>>capacity;
  95.  
  96.         capacities[from][to] = capacity;
  97.         graph[from].push_back(to);
  98.  
  99.         graph[to].push_back(from);
  100.     }
  101.  
  102.     int maxFlow = edmondsKarp(source, sink);
  103.  
  104.     cout<<endl<<endl<<"Max Flow is:"<<maxFlow<<endl;
  105.  
  106.     getch();
  107. }

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.

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.