Algorithms: Maximum flow It is defined as the maximum amount of flow that the ne

Question

Algorithms: Maximum flow

It is defined as the maximum amount of flow that the network would allow to flow from source to sink. Multiple algorithms exist in solving the maximum flow problem. Two major algorithms to solve these kind of problems are Ford-Fulkerson algorithm and Dinic's Algorithm. They are explained below.

Ford-Fulkerson Algorithm:
It was developed by L. R. Ford, Jr. and D. R. Fulkerson in 1956. A pseudocode for this algorithm is given below,

Inputs required are network graph G, source node S and sink node T.

An augmenting path is a simple path from source to sink which do not include any cycles and that pass only through positive weighted edges. A residual network graph indicates how much more flow is allowed in each edge in the network graph. If there are no augmenting paths possible from S to T, then the flow is maximum. The result i.e. the maximum flow will be the total flow out of source node which is also equal to total flow in to the sink node.

Explanation / Answer

#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
#define N 6

* It fills parent[] to store the path.if there is a path from source 's' to sink 't' in
residual graph. it returns true */

bool bfs(int resiGraph[N][N], int s, int t, int parent[])
{

    // Create a visited array and mark all vertices as not visited
    bool visited[N];
    memset(visited, 0, sizeof(visited));
    // Create a queue, enqueue source vertex and mark source vertex
    // as 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<N; v++)
        {
            if (visited[v]==false && resiGraph[u][v] > 0)
            {
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }
    // It returns true if we reached sink in BFS starting from source,
    // else false
    return (visited[t] == true);
}
int fordFulkerson(int graph[N][N], int s, int t)
{
    int u, v;
   // Create a residual graph and fill the residual graph with
    // given capacities in the original graph as residual capacities
    // in residual graph
    int resiGraph[N][N];
                     // Residual graph where resiGraph[i][j] shows
                     // residual capacity of edge from i to j (if there
                     // is an edge. If resiGraph[i][j] is 0, then there is not)
                   
                   
    for (u = 0; u < N; u++)
        for (v = 0; v < N; v++)
             resiGraph[u][v] = graph[u][v];

    int parent[N];

    int max_flow = 0;
    while (bfs(resiGraph, s, t, parent))
    {

        int path_flow = INT_MAX;
        for (v=t; v!=s; v=parent[v])
        {
            u = parent[v];
            path_flow = min(path_flow, resiGraph[u][v]);
        }
        //residual capacities of the edges and reverse edges
        // along the path get updated
        for (v=t; v != s; v=parent[v])
        {
            u = parent[v];
            resiGraph[u][v] -= path_flow;
            resiGraph[v][u] += path_flow;
        }
        // Add path flow to overall flow
        max_flow += path_flow;
    }

    return max_flow;
}
int main()
{

    int graph[N][N] = { {0, 15, 13, 0, 0, 0},
                        {0, 0, 10, 12, 0, 0},
                        {0, 4, 0, 0, 13, 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) << endl;

    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.