Graph algorithms / interactive lesson

Ford-Fulkerson & Edmonds-Karp Maximum Flow

Compare Ford-Fulkerson DFS with Edmonds-Karp BFS. Transform matching, routing, scheduling, and storage problems into flow networks, then inspect residual paths, bottlenecks, forward pushes, and backward repairs.

University Guided lesson

Choose a reducible problem

Choose the augmenting-path strategy

Snapshot 1/82

Original problem

Classic maximum-flow network

Send as much flow as possible from source S to sink T through a directed network with fixed edge capacities.

Directed edgeCapacity

S -> A, S -> B16, 13

A -> B, B -> A10, 4

A -> C, B -> D12, 14

C -> B, D -> C9, 7

C -> T, D -> T20, 4

Objective: Maximise the total source-to-sink flow.

Transformation and flow timeline

Classic maximum-flow network

About the algorithm

Ford-Fulkerson is a method for computing maximum flow in a capacitated directed network. Repeatedly find a residual path from source to sink and augment it by its bottleneck capacity. Edmonds-Karp is the same method with one disciplined choice: use breadth-first search, so every chosen path has the fewest residual edges.

History

Lester Ford Jr. and Delbert Fulkerson published their augmenting-path method in 1956. Jack Edmonds and Richard Karp showed in 1972 that choosing paths with breadth-first search gives a polynomial running-time guarantee. The residual graph is the key idea behind both variants.

Residual edges and repair

A forward residual edge represents unused capacity. A backward residual edge represents flow that may be cancelled. Backward augmentation does not physically send material backward: it repairs an earlier routing decision so capacity can be reused more effectively elsewhere.

Why reductions matter

Maximum flow is a reusable modelling tool. Bipartite matching, edge-disjoint paths, vertex-disjoint paths, preemptive scheduling, and warehouse allocation can all be transformed into capacity networks. Once the reduction is correct, the same flow engine solves every case.

Complexity

Ford-Fulkerson with integral capacities runs in O(E * |f*|), where |f*| is the maximum-flow value, but poor path choices can be costly. Edmonds-Karp uses BFS and runs in O(V * E^2), independent of capacity magnitudes.

Code companion

Connect each visual decision to an implementation pattern.

flow = zero flow

while residual path source -> sink exists:
  path = chooseAugmentingPath(residualGraph)
  bottleneck = minimum residual capacity on path

  for arc in path:
    if arc is forward:
      flow[arc.edge] += bottleneck
    else:
      flow[arc.edge] -= bottleneck

return flow

// Ford-Fulkerson: choose path with DFS
// Edmonds-Karp: choose shortest residual path with BFS