Edmonds-Karp Algorithm

@edmondskarp_algorithm

The Edmonds-Karp algorithm is a method to find the maximum flow in a network by repeatedly finding the shortest path (in terms of edges) from source to sink and pushing flow through it.

Pseudo-code
function edmonds_karp(graph, s, t):
    create residual_graph from graph
    flow <- 0

    while true:
        initialize queue
        enqueue s into queue
        initialize parent array with -1
        parent[s] <- s

        while queue is not empty:
            u <- dequeue from queue
            for each neighbor v of u:
                if parent[v] == -1 and residual_graph[u][v] > 0:
                    parent[v] <- u
                    enqueue v

        if parent[t] == -1:
            break

        path_flow <- INF
        v <- t
        while v != s:
            u <- parent[v]
            path_flow <- min(path_flow, residual_graph[u][v])
            v <- u

        v <- t
        while v != s:
            u <- parent[v]
            residual_graph[u][v] <- residual_graph[u][v] - path_flow
            residual_graph[v][u] <- residual_graph[v][u] + path_flow
            v <- u

        flow <- flow + path_flow

    return flow
  • s s is the source node, where everything starts flowing from. Think of it like a water tank.
  • t t is the sink node, where everything wants to end up. Like the final destination pipe.
  • flow flow keeps track of how much total flow we have successfully sent from s to t.
  • residual_graph residual_graph shows how much capacity is still left in each pipe. It changes after every step.
  • queue queue is used in BFS to explore the graph level by level, like checking nearest paths first.
  • parent parent stores how we reached each node so we can rebuild the path from s to t.
  • INF INF represents a very large number, meaning 'no limit' when we start checking flow.
Recipe Steps
1

Imagine a system of pipes carrying water from a source to a destination. Each pipe has a limit on how much water it can carry.

2

First, try to find a path from start to end using the shortest route possible (fewest pipes). This is like finding the quickest path on a map.

3

Check how much water can flow through that path. This depends on the smallest pipe in the path, like the weakest link.

4

Send that amount of water through the path and reduce the available space in each pipe.

5

Update the system so it knows some capacity is used, and also allow 'undo' flow if needed (this is why we add reverse edges).

6

Repeat finding new shortest paths and pushing flow until no more paths from source to sink exist.

7

The total amount of water you successfully sent is your final answer.

Questions & Answers

Because BFS finds the shortest path in terms of edges, which helps keep the algorithm efficient and predictable.

It is the smallest capacity edge in the path, which limits how much flow can go through.

To allow the algorithm to adjust or 'undo' previous flow if a better path is found later.

When there is no path from source to sink with remaining capacity.
- The algorithm works by repeatedly finding paths and pushing flow through them.
- Each time we choose the shortest path using BFS.
- The smallest edge capacity in a path controls how much flow we can send.
- Residual graphs are updated every step to track remaining capacity.
- Reverse edges are important because they allow correcting earlier decisions.
- The process stops when no more valid paths exist from source to sink.

Related Algorithms
Dinic's Algorithm

Dinic's Algorithm finds the maximum flow in a network by building layers using BFS and then sending flow using DFS in these layers, making it faster than simpler methods.

View