Max Flow Problem – Ford-Fulkerson Algorithm

Objective: Given a directed graph which represents a flow network involving source(S) vertex and Sink (T) vertex.  Each edge in the graph has an individual capacity which is the maximum flow that edge allows.

Flow in the network has following restrictions-

  • Input flow must match to output flow for each node in the graph, except source and sink node.
  • Flow out from source node must match with flow in to sink node.
  • Flow from each edge should not exceed the capacity of that node.

Write an algorithm to find the maximum flow possible from source (S) vertex to sink (T) vertex.

Example:

Given the graph, each edge has a capacity (the maximum unit can be transfer between two vertices). Find out the maximum flow which can be transfer from source vertex (S) to sink vertex (T).

We strongly recommend reading the following article before continue reading

  1. Max Flow problem – Introduction
  2. Graph – Breadth-First Search

Ford-Fulkerson Algorithm:

In simple terms, Ford-Fulkerson Algorithm is : As long as there is a path from source(S) node to sink(T) node with available capacity on all the edges in the path, send the possible flow from that path and find the another path and so on. Path with available capacity is called augmenting path.

Pseudo Code:

Inputs Given a Network G = (V, E) with flow capacity c, a source node s, and a sink node t

Output: Compute a flow f from s to t.

  1. Initialize max_flow←0
  2. Initialize f(u,v)← cf (u, v)  for edges (u, v).
  3. While there is a path p from s to t in Gf (residual graph), such that flow capacity, cf (u, v) > 0 for all the edges (u, v) in path p
    • Find cf(p) = min{cf(u, v): (u, v) p } (flow possible in path p. pick the minimum capacity among all edges).
    • Add max_flow = max_flow + cf(p)
    • For each edge (u, v) in path p
      • f(u, v) ← f(u, v) – cf(p) (reduce the capacity of each edge in path)
      • f(v, u) ←f(v, u) + cf(p) (The flow will returned by back edge, might get used later).
  4. Return max_flow.

Let’s understand the above pseudo code in detail

  1. Initialize max_flow  = 0 (this will be final answer) and initialize flow for each edge in graph as the capacity of that edge.
  2. Find the path(p) from source s to sink t where in each edge in path has capacity > 0. Do Breadth-first search to find the path.
  3. Find the maximum flow possible among that path found (it be the minimum capacity among all edges in the path) in previous step and add it to the max_flow.
  4. Update the residual graph, reduce the each edge capacity by flow possible in previous step and add the flow in the reverse edge, add the reverse edge if needed (Please read this if you don’t know about residual graph).
  5. Repeat the steps from b to d till there is path from source to sink.
  6. Return max_flow.

previous arrow
next arrow
PlayPause
Slider

Java Program:

Output:

Maximum flow from source: 0 to destination: 5 is: 15

Notes:

  • Ford-Fulkerson algorithm is also called Ford-Fulkerson method.
  • It is called method instead of algorithm since approach to find the augmenting path in residual graph has many implementations with different run times.
  • It is a greedy algorithm.
  • Ford–Fulkerson is often also used for the Edmonds–Karp algorithm, which is a fully defined implementation of the Ford–Fulkerson method.

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: