Ford-Fulkerson Algorithm for Maximum Flow Problem

Learn via video course
View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
Start Learning
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
Start Learning
Topics Covered


In Graph Theory, maximum flow is the maximum amount of flow that can flow from source node to sink node in a given flow network.

Ford-Fulkerson method implemented as per the Edmonds-Karp algorithm is used to find the maximum flow in a given flow network.


The Ford-Fulkerson algorithm is used to detect maximum flow from start vertex to sink vertex in a given graph. In this graph, every edge has the capacity.


If we consider a rail network that connects two cities (say AA and BB) by way of several intermediate cities, where each railway line has some value assigned to it denoting its capacity.

Ford-Fulkerson Algorithm for Maximum Flow Problem

Flow can be defined as any physical/virtual thing that we can transmit between two vertices through an edge in a graph, for example - water, current, data and in this case "trains".

Assuming steady conditions (Number of trains on a railway track at any instance of time must not exceeds the track's capacity), if we need to find what is the maximum number of trains (maximum flow) that we can send from City AA to city BB then the problem is known as the "Maximum Flow Problem". Before introducing the problem formally firstly let's have a look at some terminologies for a better understanding of the problem and its solution.

Flow Network

In graph theory, a flow network is defined as directed graph G=(V,E)G=(V,E) constrained with a function cc, which bounds each edge ee with a non-negative integer value which is known as capacitycapacity of the edge ee with two additional vertices defined as source SS and sink TT.

As shown in the flow network given below, a source vertex has all outgoing edges and no incoming edges, more formally we can say In_degree[source]=0 and sink vertex has all incoming edges and no outgoing edge more formally out_degree[sink]=0.

Flow Network

Also, any flow network should satisfy all the underlying conditions --

  • For all the vertices (except the source and the sink vertex), input flow must be equal to output flow.
  • For any given edge(EiE_i) in the flow network, 0flow(Ei)capacity(Ei)\leq flow(E_i)\leq capacity(E_i) must hold, we can not send more flow through an edge than its capacity.
  • Total outflow from the source vertex must be equal to total inflow to the sink vertex.

Maximum Flow Problem Introduction

The underlying image represents a flow network, where the first value of each edge represents the amount of the flow through it (which is initially set to 0) and the second value represents the capacity of the edge.

Maximum Flow Problem

The maximum flow is the maximal possible value of the flow of the network where the flow is defined as, "sum of all the flow that gets produced in source ss, or sum of all the flow that gets consumed in the sink tt ".

If we try to co-relate this problem with a real-life problem, we can visualize all the edges as water pipes, where the capacity of edge (here pipe) is the maximum amount of water that can flow through it per unit time. Where ss is analogous to the Water plant and tt is analogous to the drainage plant.

maximum flow real lifep problem

It follows the conditions necessary for a flow network that more water than pipe's capacity can't flow through it and water inflow and outflow of water at every vertex (house) must be equal as water can't magically disappear or appear.

Formally, Maximum flow can be defined as -

Maximum amount of flow that the network would allow to flow from source to sink vertex.

Two major algorithms are there to solve this kind of problem viz. Ford-Fulkerson Algorithm and other is Dinic's Algorithms of which Ford-Fulkerson algorithm is explained below --

A Naive Greedy Algorithm

The naive approach that comes to our mind is a greedy algorithm that involves finding a path from the source node (ss) to the sink node (tt) and if the path exists then increasing the flow as much as possible such that along any edge do not exceed its capacity.

Let's look at the algorithm -

E = number of the edges in the flow network. f(e)f(e) = flow along the edge edge ee. c(e)c(e) = Capacity of the edge ee.

  • Initialize the maxFlow with 0 i.e.i.e. maxFlow=0
  • Use BFS/DFS to search for a path between the vertices ss and tt. Here existence of path PP means, for every edge ee in PP, f(e)<c(e)f(e) < c(e) must hold. If such a path exists then -
    • flowCanBeAdded = min(c(e)f(e))min(c(e)-f(e)) for each edge ee in PP.
    • maxFlow = maxFlow + flowCanBeAdded
    • For each edge ee in PP, f(e)=f(e)+f(e)=f(e)+flowCanBeAdded
  • In the other case (There does not exist any path between ss and tt) return the maxFlow.

Let's try the above algorithm on the underlying flow network -

A Naive Greedy Algorithm

According to the algorithm, in the above flow network, we will search for a path between ss and tt. Let's assume we choose the path sBAts\rightarrow B \rightarrow A \rightarrow t with capacities as 5,10,45, 10, 4. The minimum among them is 44, so we will increase that much flow along the path, after which our flow network will look like -

naive greedy algorithm flow network

Now we are not left with any other valid path between ss and tt so according to the algorithm, the maximum flow is 44.

But, it is easily noticeable that the maximum flow that can be obtained is 88 by choosing the paths sAts\rightarrow A \rightarrow t and sBts\rightarrow B \rightarrow t. So we can say that the greedy algorithm doesn't give the correct answer always. To obviate this difficulty we use the Ford-Fulkerson method that uses the concept of residual graph which has been discussed in detail in the next section.

Ford-Fulkerson Algorithm for finding Maximum Flow

This algorithm was developed by L.R. Ford and Dr. R. Fulkerson in 1956. Before diving deep into the algorithms let's define two more things for better understanding at later stages -

  • Residual Capacity - Residual capacity of the directed edge is nothing but capacity of the edge - current flow through the edge. If there is flow along a directed edge u → v then reversed edge has a capacity 0 and we can say f(v,u)=f(u,v)f(v,u)=-f(u,v)
  • Residual Graph - Residual graph is nothing but the same graph with the only difference is we use residual capacities as capacities.
  • Augmenting Path - It is a simple path from source to sink in a residual graph i.e. along the edges whose capacity is 00.

In the Ford-Fulkerson method, firstly we set the flow of each edge ee to 00. Then we look if an augmenting path exists between ss and tt. If such a path exists then we will increase the flow along those edges.

We repeat this process until there is at least on more augmenting path in the residual graph. Once there are no more augmenting paths maximal flow is achieved.

Let us see what does increasing the flow along an augmenting path means. Let XX be the minimum residual capacity found among the edges of augmenting path.

Then, for every edge (u,v)(u, v) in the path we do f(u,v)+=Xf(u,v)+=X (Forward edges) and f(v,u)=Xf(v, u)-=X (backward edges).

Now we use the above network to demonstrate how the Ford-Fulkerson method works.


Fordm Fulkerson method finding Maximum Flow

We can see that the initial flow of all the paths is 00. Now we will search for an augmenting path in the network.

One such path is sABts \rightarrow A \rightarrow B \rightarrow t with residual capacities as 77, 55, and 88. Their minimum is 55, so as per the Ford-Fulkerson method we will increase a flow of 55 along the path.

finding Maximum Flow example

Now, we will check for other possible augmenting paths, one such path can be sDCts \rightarrow D\rightarrow C\rightarrow t with residual capacities as 44, 22, and 55 of which 22 is the minimum. So we will increase a flow of 22 along the path.

finding Maximum Flow example one

One can easily observe from the figure that we can't increase the flow along paths ABA \rightarrow B and DCD \rightarrow C as their flow has reached their maximum capacity. So to find other augmenting paths, we must take care that these edges must not be part of the path.

One such path can be sDACtwithresidualcapacitiesass\rightarrow D \rightarrow A\rightarrow C \rightarrow t with residual capacities as 2,, 3,, 3,and, and 3ofwhichof which2istheminimumsowillincreaseaflowofis the minimum so will increase a flow of2$ along the path.

finding Maximum Flow example two

An augmenting path that is possible in the current residual network is sACts\rightarrow A \rightarrow C \rightarrow t with residual capacities as 22, 11, and 11 of which 11 is minimum.

So we will increase the flow of 11 along the path after which our network will look like -

finding Maximum Flow example three

Now there are no more augmenting paths possible in the network, so the maximum flow is the total flow going out of source or total flow coming in sink i.e. 6+4=5+5=106+4=5+5=10



To keep things simple, we are using adjacency matrix implementation of the graph. The flow of writing code will be -

  • Making a residual graph from the values of the given graph.
  • Declaring a parent array of size VV to store the augmenting path during BFS.
  • Finding the bottle-neck capacity (minimum residual capacity) of the augmenting path.
  • Updating residual capacities of edges and reverse edges.
  • Increasing the overall path flow.
  • Returning answer i.e. maximum flow.

C/C++ implementation of Ford-Fulkerson Method

Java implementation of Ford-Fulkerson Method

C# Implementation of Ford-Fulkerson Method


Complexity Analysis

The above implementation of the Ford-Fulkerson algorithm is called Edmonds-Karp Algorithm. The idea of Edmonds-Karp is to use BFS to find the augmenting path in the residual network.

Because we can implement each iteration of the Ford-Fulkerson Method in O(E)O(E). As we use BFS to find augmenting path (Edmonds-Karp implementation) overall time complexity would be O(VE2)O(V*E^2) in the worst case. Since, Adajency Matrix representation of the graph is used in the above implementation therefore, BFS would take O(V2)O(V^2) time, and hence the overall time complexity is O(EV3)O(E*V^3).


  • In traffic movements, to find how much traffic can move from a City AA to City BB.
  • In electrical systems, to find the maximum current that could flow the wires without causing any short circuit.
  • In the water/sewage management system, to find maximum capacity of the network.


  • In this article, we have seen what is maximal flow problem how to find it in a given network graph.
  • We have seen different terminologies like Residual capacity, residual graph, augmenting path, bottleneck capacity, etc.
  • We have seen the Ford-Fulkerson method to find a maximal flow of a network graph along with its code in three different languages and its time complexity.

Code with Confidence! Enroll in Our Online Data Structures Courses and Master Efficient Algorithms.