Graphs and Network Algorithms · Network Flow

Ford-Fulkerson Algorithm

Ford-Fulkerson increases flow through augmenting paths until no more improvement is possible.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

This is advanced enrichment for students ready for network optimization ideas.

Guided Lesson Notes

Understanding Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm focuses on relationships, reachability, paths, cycles, connectivity, and optimization over edges. Ford-Fulkerson increases flow through augmenting paths until no more improvement is possible.

Model: draw vertices as dots and edges as connections; then decide whether direction, weight, or capacity matters.

Invariant: visited, distance, parent, component, or flow arrays must match what has actually been discovered so far.

Implementation: adjacency lists or matrices, queues, stacks, priority queues, union-find, and repeated edge relaxation.

Use Ford-Fulkerson Algorithm when the problem mentions roads, networks, prerequisites, components, shortest paths, spanning costs, or dependency order.

Visual Model

A small picture for Ford-Fulkerson Algorithm

Key Ideas

Capacities and residual graphs
Augmenting paths
Max-flow intuition

Practice Prompts

Trace one augmenting path update.
Explain residual capacity after sending flow.

Vocabulary

Terms students should be able to say clearly

Vertex

An object or state in the graph.

Edge

A relationship or move between vertices.

Path

A sequence of edges from one vertex to another.

Cycle

A path that returns to a previous vertex.

Component

A group of vertices connected by reachability.

Relaxation

Trying to improve a known distance or cost through an edge.

Worked Example

Worked example: tracing Ford-Fulkerson Algorithm

Trace a small input, focusing on capacities and residual graphs.

1Write a small input where Ford-Fulkerson Algorithm is clearly useful.
2Label the part of the input related to Capacities and residual graphs.
3Perform one operation and explain which invariant is still true afterward.
4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

Operation	Typical Cost	Reason
Adjacency-list traversal	O(V + E)	DFS and BFS visit vertices and inspect edges.
Adjacency matrix storage	O(V^2)	A matrix reserves space for every possible pair.
Weighted optimization	Varies	MST and shortest-path algorithms depend on sorting, heaps, and graph density.

Common Mistakes

What to watch while practicing

Coding before drawing the structure or state changes.
Forgetting the invariant that makes the algorithm correct.
Testing only the sample input and skipping boundary cases.
Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Ford-Fulkerson Algorithm interview problem: Maximum Flow Between Two Servers

Interview hard

Problem

Given a directed network with capacities, compute the maximum amount of flow that can be sent from source to sink.

Input

The first line contains n, m, source, and sink. The next m lines contain u v capacity using 0-based node labels.

Output

Print the maximum flow value.

Sample Input

Sample Output

Why the sample works

The source can send 3 units through node 1 and 2 units through node 2, for a total flow of 5.

Approach

1Maintain a residual capacity graph.
2Use BFS to find an augmenting path from source to sink.
3Push the bottleneck capacity along that path.
4Repeat until no augmenting path remains.

O(VE^2) time for Edmonds-Karp and O(V^2) residual space.

Java Solution

import java.util.*;

public class Main {
  static int bfs(int[][] cap, int source, int sink, int[] parent) {
    Arrays.fill(parent, -1);
    parent[source] = source;
    Queue<int[]> q = new ArrayDeque<>();
    q.add(new int[] {source, Integer.MAX_VALUE});

    while (!q.isEmpty()) {
      int[] cur = q.remove();
      int node = cur[0];
      int flow = cur[1];

      for (int next = 0; next < cap.length; next++) {
        if (parent[next] == -1 && cap[node][next] > 0) {
          parent[next] = node;
          int nextFlow = Math.min(flow, cap[node][next]);
          if (next == sink) return nextFlow;
          q.add(new int[] {next, nextFlow});
        }
      }
    }

    return 0;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int source = sc.nextInt();
    int sink = sc.nextInt();

    int[][] cap = new int[n][n];
    for (int i = 0; i < m; i++) {
      int u = sc.nextInt();
      int v = sc.nextInt();
      int c = sc.nextInt();
      cap[u][v] += c;
    }

    int[] parent = new int[n];
    int maxFlow = 0;
    int pushed;

    while ((pushed = bfs(cap, source, sink, parent)) > 0) {
      maxFlow += pushed;
      int cur = sink;
      while (cur != source) {
        int prev = parent[cur];
        cap[prev][cur] -= pushed;
        cap[cur][prev] += pushed;
        cur = prev;
      }
    }

    System.out.println(maxFlow);
  }
}

Python Solution

from collections import deque

n, m, source, sink = map(int, input().split())
cap = [[0] * n for _ in range(n)]
for _ in range(m):
    u, v, c = map(int, input().split())
    cap[u][v] += c

def bfs():
    parent = [-1] * n
    parent[source] = source
    q = deque([(source, 10 ** 18)])

    while q:
        node, flow = q.popleft()
        for nxt in range(n):
            if parent[nxt] == -1 and cap[node][nxt] > 0:
                parent[nxt] = node
                next_flow = min(flow, cap[node][nxt])
                if nxt == sink:
                    return next_flow, parent
                q.append((nxt, next_flow))

    return 0, parent

max_flow = 0
while True:
    pushed, parent = bfs()
    if pushed == 0:
        break
    max_flow += pushed
    cur = sink
    while cur != source:
        prev = parent[cur]
        cap[prev][cur] -= pushed
        cap[cur][prev] += pushed
        cur = prev

print(max_flow)

Practice Challenge

Make the idea your own

Create a two-minute explanation of Ford-Fulkerson Algorithm: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free Session Text Us Open Online Compiler