C++ Program to Implement Network Flow Problem

This C++ Program demonstrates implementation of Network_Flow Problem.

Here is source code of the C++ Program to demonstrate Network_Flow Problem.
The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Network Flow Problem
  3.  */
  4. #include <iostream>
  5. #include <climits>
  6. #include <cstring>
  7. #include <queue>
  8. #define V 6
  9. using namespace std;
  10.  
  11. /*
  12.  *  Returns true if there is a path from source 's' to sink 't' in
  13.  * residual graph. Also fills parent[] to store the path *
  14.  */
  15. bool bfs(int rGraph[V][V], int s, int t, int parent[])
  16. {
  17.     bool visited[V];
  18.     memset(visited, 0, sizeof(visited));
  19.     queue <int> q;
  20.     q.push(s);
  21.     visited[s] = true;
  22.     parent[s] = -1;
  23.     while (!q.empty())
  24.     {
  25.         int u = q.front();
  26.         q.pop();
  27.  
  28.         for (int v=0; v<V; v++)
  29.         {
  30.             if (visited[v]==false && rGraph[u][v] > 0)
  31.             {
  32.                 q.push(v);
  33.                 parent[v] = u;
  34.                 visited[v] = true;
  35.             }
  36.         }
  37.     }
  38.     return (visited[t] == true);
  39. }
  40.  
  41. /*
  42.  *  Returns tne maximum flow from s to t in the given graph
  43.  */
  44. int fordFulkerson(int graph[V][V], int s, int t)
  45. {
  46.     int u, v;
  47.     int rGraph[V][V];
  48.     for (u = 0; u < V; u++)
  49.     {
  50.         for (v = 0; v < V; v++)
  51.              rGraph[u][v] = graph[u][v];
  52.     }
  53.     int parent[V];
  54.     int max_flow = 0;
  55.  
  56.     while (bfs(rGraph, s, t, parent))
  57.     {
  58.         int path_flow = INT_MAX;
  59.         for (v=t; v!=s; v=parent[v])
  60.         {
  61.             u = parent[v];
  62.             path_flow = min(path_flow, rGraph[u][v]);
  63.         }
  64.         for (v = t; v != s; v = parent[v])
  65.         {
  66.             u = parent[v];
  67.             rGraph[u][v] -= path_flow;
  68.             rGraph[v][u] += path_flow;
  69.         }
  70.         max_flow += path_flow;
  71.     }
  72.     return max_flow;
  73. }
  74. /*
  75.  * Main Contains Menu
  76.  */ 
  77. int main()
  78. {
  79.     int graph[V][V] = { {0, 16, 13, 0, 0, 0},
  80.                         {0, 0, 10, 12, 0, 0},
  81.                         {0, 4, 0, 0, 14, 0},
  82.                         {0, 0, 9, 0, 0, 20},
  83.                         {0, 0, 0, 7, 0, 4},
  84.                         {0, 0, 0, 0, 0, 0}
  85.                       };
  86.  
  87.     cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);
  88.  
  89.     return 0;
  90. }

$ g++ nwtwork_flow.cpp
$ a.out
The maximum possible flow is 23
 
------------------
(program exited with code: 0)
Press return to continue

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

advertisement
advertisement
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]

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.