C++ Program to Implement Ford Fulkerson Algorithm

This C++ program displays the Ford-Fulkersson Algorithm which computes the maximum flow present inside a network.

Here is the source code of the C++ program to display the maximum flow present inside a directed graph given as an input. 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 Ford–Fulkerson Algorithm
  3.  */
  4. #include <iostream>
  5. #include <string.h>
  6. #include <queue>
  7. using namespace std;
  8. bool bfs(int rGraph[][6], int s, int t, int parent[])
  9. {
  10.     bool visited[6];
  11.     memset(visited, 0, sizeof(visited));
  12.     queue <int> q;
  13.     q.push(s);
  14.     visited[s] = true;
  15.     parent[s] = -1;
  16.  
  17.     while (!q.empty())
  18.     {
  19.         int u = q.front();
  20.         q.pop();
  21.         for (int v = 0; v < 6; v++)
  22.         {
  23.             if (visited[v] == false && rGraph[u][v] > 0)
  24.             {
  25.                 q.push(v);
  26.                 parent[v] = u;
  27.                 visited[v] = true;
  28.             }
  29.         }
  30.     }
  31.     return (visited[t] == true);
  32. }
  33.  
  34. int fordFulkerson(int graph[6][6], int s, int t)
  35. {
  36.     int u, v;
  37.     int rGraph[6][6];  
  38.     for (u = 0; u < 6; u++)
  39.     {
  40.         for (v = 0; v < 6; v++)
  41.         {
  42.             rGraph[u][v] = graph[u][v];
  43.         }
  44.     }
  45.     int parent[6];
  46.     int max_flow = 0;
  47.     while (bfs(rGraph, s, t, parent))
  48.     {
  49.         int path_flow = INT_MAX;
  50.         for (v = t; v != s; v = parent[v])
  51.         {
  52.             u = parent[v];
  53.             path_flow = min(path_flow, rGraph[u][v]);
  54.         }
  55.         for (v = t; v != s; v = parent[v])
  56.         {
  57.             u = parent[v];
  58.             rGraph[u][v] -= path_flow;
  59.             rGraph[v][u] += path_flow;
  60.         }
  61.         max_flow += path_flow;
  62.     }
  63.     return max_flow;
  64. }
  65. int main()
  66. {
  67.     int graph[6][6] = { {0, 16, 13, 0, 0, 0},
  68.                         {0, 0, 10, 12, 0, 0},
  69.                         {0, 4, 0, 0, 14, 0},
  70.                         {0, 0, 9, 0, 0, 20},
  71.                         {0, 0, 0, 7, 0, 4},
  72.                         {0, 0, 0, 0, 0, 0}
  73.                       }; 
  74.     cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);
  75.     getch();
  76. }

Output
The maximum possible 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.