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.

`/*`

`* C++ Program to Implement Network Flow Problem`

`*/`

`#include <iostream>`

`#include <climits>`

`#include <cstring>`

`#include <queue>`

`#define V 6`

using namespace std;

`/*`

`* Returns true if there is a path from source 's' to sink 't' in`

`* residual graph. Also fills parent[] to store the path *`

`*/`

bool bfs(int rGraph[V][V], int s, int t, int parent[])

`{`

bool visited[V];

memset(visited, 0, sizeof(visited));

queue <int> q;

q.push(s);

visited[s] = true;

parent[s] = -1;

while (!q.empty())

`{`

int u = q.front();

q.pop();

for (int v=0; v<V; v++)

`{`

if (visited[v]==false && rGraph[u][v] > 0)

`{`

q.push(v);

parent[v] = u;

visited[v] = true;

`}`

`}`

`}`

return (visited[t] == true);

`}`

`/*`

`* Returns tne maximum flow from s to t in the given graph`

`*/`

int fordFulkerson(int graph[V][V], int s, int t)

`{`

int u, v;

int rGraph[V][V];

for (u = 0; u < V; u++)

`{`

for (v = 0; v < V; v++)

rGraph[u][v] = graph[u][v];

`}`

int parent[V];

int max_flow = 0;

while (bfs(rGraph, s, t, parent))

`{`

int path_flow = INT_MAX;

for (v=t; v!=s; v=parent[v])

`{`

u = parent[v];

path_flow = min(path_flow, rGraph[u][v]);

`}`

for (v = t; v != s; v = parent[v])

`{`

u = parent[v];

rGraph[u][v] -= path_flow;

rGraph[v][u] += path_flow;

`}`

max_flow += path_flow;

`}`

return max_flow;

`}`

`/*`

`* Main Contains Menu`

`*/`

int main()

`{`

int graph[V][V] = { {0, 16, 13, 0, 0, 0},

{0, 0, 10, 12, 0, 0},

{0, 4, 0, 0, 14, 0},

{0, 0, 9, 0, 0, 20},

{0, 0, 0, 7, 0, 4},

{0, 0, 0, 0, 0, 0}

};

cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);

return 0;

`}`

$ 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.**

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