Graph Theory37 sections · 1633 units
Open in Course

Pseudocode - Edmonds-Karp

(BFS-based max flow)

I'll show you Edmonds Karp. It uses breadth first search (BFS) to find an augmenting path in the residual graph. Each iteration pushes bottleneck flow.

function maxFlow(s, t):
    flow = 0
    while true:
        parent = bfs(s, t)
        if parent[t] is null:
            break
        add = INF
        v = t
        while v != s:
            u = parent[v]
            add = min(add, cap[u][v])
            v = u
        v = t
        while v != s:
            u = parent[v]
            cap[u][v] = cap[u][v] - add
            cap[v][u] = cap[v][u] + add
            v = u
        flow = flow + add
    return flow

BFS bounds the number of augmentations. The algorithm runs in O(VE2)O(VE^2) time and uses O(V+E)O(V + E) space.