AlgoVerse

Maximum flow (Edmonds–Karp)

While the residual network has a path from the source to the last node, find the shortest one with BFS and push flow along it.

Every edge has a capacity. We want to send as much flow as possible from the source (the chosen node) to the sink (the last node), never exceeding an edge's capacity, with everything that enters a node also leaving it.

Read the full explanation ↓
Input:
V=6 · E=9 · src=SPDF export

The well-known six-node network from S to T; the maximum flow is 23.

  1. from collections import deque
  3. INF = float("inf")
  6. def edmonds_karp(graph, s):
  7. t = list(graph)[-1] # the last node is the sink
  8. cap = {u: {} for u in graph}
  9. for u in graph:
  10. for v, w in graph[u]:
  11. cap[u][v] = cap[u].get(v, 0) + w
  12. cap[v].setdefault(u, 0)
  13. total = 0
  14. while True:
  15. parent = {v: None for v in graph}
  16. seen = {s}
  17. queue = deque([s])
  18. while queue and t not in seen:
  19. u = queue.popleft()
  20. for v in cap[u]:
  21. if cap[u][v] == 0 or v in seen:
  22. continue
  23. seen.add(v)
  24. parent[v] = u
  25. queue.append(v)
  26. if t not in seen:
  27. return total
  28. bottleneck = INF
  29. v = t
  30. while v != s:
  31. bottleneck = min(bottleneck, cap[parent[v]][v])
  32. v = parent[v]
  33. v = t
  34. while v != s:
  35. u = parent[v]
  36. cap[u][v] = cap[u][v] - bottleneck
  37. cap[v][u] = cap[v][u] + bottleneck
  38. v = u
  39. total = total + bottleneck

Invariant: cap[u][v] is always the residual capacity: the edge's capacity minus its flow, plus any flow that can be pushed back from the reverse edge.

Start

16131241492074SABCDT
  • Current node (u)
  • Search tree (from parent)
  • Edge being checked

Queue queue

empty

Local variables

s'S'

Orange = changed in this step

graph dict
  • 'S': [('A', 16), ('B', 13)]
  • 'A': [('C', 12)]
  • 'B': [('A', 4), ('D', 14)]
  • 'C': [('B', 9), ('T', 20)]
  • 'D': [('C', 7), ('T', 4)]
  • 'T': []

Call stack

  1. edmonds_karp()line 6
Step 1 of 413
Black = search · Orange = key stepsearch: 0/4 · take: 0/17 · reach: 0/18 · bottleneck: 0/3 · push: 0/10 · augment: 0/3 · no_path: 0/1

    How the work grows with input size

    Average of 5 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • take
    • push
    • current input (n=6)
    01020304812n = number of nodestakepush
    Show as a table
    ntakepush
    47.85.2
    820.48.8
    1228.211.6
    Explanation

    The idea

    Every edge has a capacity. We want to send as much flow as possible from the source (the chosen node) to the sink (the last node), never exceeding an edge's capacity, with everything that enters a node also leaving it.

    The Ford–Fulkerson method

    1. Find a path from the source to the sink in the residual network (the capacity that is still free): an augmenting path.
    2. Send the smallest capacity on the path (the bottleneck).
    3. For every edge u → v that got flow, give the reverse edge v → u the same amount of capacity, so the flow can later be taken back.

    Repeat while an augmenting path exists. The max-flow min-cut theorem says the final answer is optimal.

    Why BFS?

    Edmonds and Karp showed that if we always take the shortest path (with BFS), there are at most O(V·E) rounds: O(V·E²) in total, no matter how large the capacities are.

    What to watch in the trace

    • The coloured edges are the current BFS tree; the augmenting path lies on it.
    • The cap dictionary in the memory panel holds the residual capacities; "taking flow back" shows a reverse edge in use.