Maximum flow is built by sending as much flow as possible from a source vertex to a sink vertex across directed edges with fixed capacity limits. Edmonds-Karp handles that by repeating the same pass until the sink can no longer be reached through edges that still have room left. Its main rule comes from breadth-first search, which picks the next augmenting route with the fewest edges in the current residual graph. That choice gives the algorithm a predictable O(V * E^2) time bound and keeps the Java implementation relatively easy to follow because every pass uses a queue, records parent links, finds the bottleneck value, updates residual capacities, and adds that bottleneck to the total flow.
Flow Network Mechanics
Before the Java class appears, the algorithm depends on two ideas that need to stay separate. Capacity tells us how much flow an edge is allowed to carry. The residual graph tells us how much room remains after flow has already moved, including how much earlier flow can be canceled in the reverse direction. Edmonds-Karp moves between those ideas on every pass. BFS finds a usable source-to-sink route in the residual graph, the smallest remaining capacity on that route controls the next flow increase, and the residual graph changes before the next BFS begins.
Capacity
Every directed edge in a flow network has a limit. If edge 0 -> 1 has capacity 3, that edge can carry 0, 1, 2, or 3 units of flow, but it cannot carry 4. The capacity is not a cost, a priority, or a distance. It is only the upper bound on how much flow can move across that edge in that direction.
The source vertex is where flow leaves the network. The sink vertex is where flow reaches its final target. Middle vertices follow a conservation rule, which means flow entering a middle vertex must leave through outgoing edges. If vertex 1 receives 2 units from the source, vertex 1 cannot keep those units. We need outgoing capacity from 1 so those units can continue toward the sink.
We can represent the starting network as edge records before building the full max flow class:
import java.util.List;
class CapacityInputDemo {
record CapacityEdge(int from, int to, long capacity) { }
public static void main(String[] args) {
List<CapacityEdge> edges = List.of(
new CapacityEdge(0, 1, 3),
new CapacityEdge(0, 2, 2),
new CapacityEdge(1, 2, 1),
new CapacityEdge(1, 3, 2),
new CapacityEdge(2, 3, 4)
);
System.out.println(edges);
}
}Those records represent the input network before any flow has moved. Vertex 0 is the source, and vertex 3 is the sink. The two outgoing edges from the source have capacities 3 and 2, so the source can send at most 5 units total. That source-side limit does not prove the final answer by itself, because the rest of the network still has to carry that same amount into the sink.
Capacity becomes easier to read when we follow a single source-to-sink route. The route 0 -> 1 -> 3 has capacities 3 and 2. The route can carry only 2 units during that pass because every unit must cross both edges. The smaller edge controls the amount that can be added.
class BottleneckDemo {
static long bottleneck(long firstEdgeCapacity, long secondEdgeCapacity) {
return Math.min(firstEdgeCapacity, secondEdgeCapacity);
}
public static void main(String[] args) {
long routeCapacity = bottleneck(3, 2);
System.out.println(routeCapacity);
}
}The printed value is 2. We are not adding the edge capacities along the route. We are taking the minimum, because the full route can only carry what its tightest edge can carry.
After sending those 2 units through 0 -> 1 -> 3, the total flow has started to grow, but the network may still have more room. The route 0 -> 2 -> 3 can carry 2 units, raising total flow from 2 to 4. Then 0 -> 1 -> 2 -> 3 can still carry 1 unit because 0 -> 1 has 1 unit left, 1 -> 2 has capacity 1, and 2 -> 3 still has room.
A small text trace can make that buildup easier to check by hand:
Pass 1
Route 0 -> 1 -> 3
Bottleneck 2
Total flow 2
Pass 2
Route 0 -> 2 -> 3
Bottleneck 2
Total flow 4
Pass 3
Route 0 -> 1 -> 2 -> 3
Bottleneck 1
Total flow 5This trace follows the same rule three times. We find a route from source to sink, read the smallest available capacity on that route, and add that value to the total flow. After the third pass, the source has no outgoing room left, because 0 -> 1 has carried 3 units and 0 -> 2 has carried 2 units.
At that point, the source side alone blocks more flow:
0 -> 1 carries 3 of 3
0 -> 2 carries 2 of 2
Total leaving source 5The numbers confirm why no later pass can raise the total above 5 in this graph. Flow cannot leave the source without remaining capacity on an outgoing edge, and both outgoing source edges are full.
Residual Graph
The residual graph is the changing graph that Edmonds-Karp searches after flow starts moving. It stores remaining forward capacity and reverse cancellation capacity. Because of that, the residual graph is not just the original input copied into a new form. It is the current state of what the algorithm can still do.
For every original directed edge u -> v, Edmonds-Karp tracks two residual directions. The forward residual edge starts with the original capacity. The reverse residual edge starts at 0. If the algorithm sends flow from u to v, the forward residual capacity drops, and the reverse residual capacity rises by the same amount.
Original edge
0 -> 1 capacity 3
Before sending flow
0 -> 1 residual 3
1 -> 0 residual 0
After sending 2 units
0 -> 1 residual 1
1 -> 0 residual 2The forward direction now has only 1 unit left. The reverse direction now has 2 units, which means the algorithm can cancel up to 2 units of the earlier 0 -> 1 flow if a later route needs that capacity back.
That reverse edge does not mean the original input had a normal edge from 1 to 0. It records the option to reduce earlier flow. Without reverse residual capacity, the algorithm would have no way to repair a choice from an earlier pass.
The same update happens for every edge on the chosen route. After sending 2 units through 0 -> 1 -> 3, both forward residual edges lose 2, and both reverse residual edges gain 2.
0 -> 1 drops from 3 to 1
1 -> 0 rises from 0 to 2
1 -> 3 drops from 2 to 0
3 -> 1 rises from 0 to 2The next BFS sees this updated residual state. Edge 1 -> 3 now has residual capacity 0, so BFS cannot follow it forward during the next pass. Edge 3 -> 1 has residual capacity 2, which represents canceling some of the earlier flow through 1 -> 3.
The residual update rule can be written with small variables:
class ResidualUpdateDemo {
public static void main(String[] args) {
long forwardResidual = 3;
long reverseResidual = 0;
long pushed = 2;
forwardResidual -= pushed;
reverseResidual += pushed;
System.out.println(forwardResidual);
System.out.println(reverseResidual);
}
}The output is 1 followed by 2. The forward edge has less room because 2 units were pushed across it. The reverse edge gained 2, so that same amount can be undone later if a future route needs to redirect flow.
Residual capacity is the reason Edmonds-Karp always searches the current graph state rather than only the original edge list. The original edge list tells us what was allowed before flow started. The residual graph tells us what is allowed now, after earlier passes have filled some edges and opened reverse cancellation room.
BFS only follows residual edges with capacity above 0. Among those available edges, it finds the source-to-sink route with the fewest edge hops. Shortest in Edmonds-Karp means fewest edges. It does not mean largest capacity, lowest cost, or smallest weight.
class ResidualSearchRuleDemo {
static boolean canFollow(long residualCapacity) {
return residualCapacity > 0;
}
public static void main(String[] args) {
System.out.println(canFollow(1));
System.out.println(canFollow(0));
}
}The first result is true, and the second result is false. During BFS, an edge with positive residual capacity can be followed. An edge with residual capacity 0 is blocked in that direction until a later residual update changes it.
We can also express the bottleneck step over residual capacities instead of original capacities:
class ResidualBottleneckDemo {
static long routeBottleneck(long[] residualCapacities) {
long smallest = Long.MAX_VALUE;
for (long capacity : residualCapacities) {
smallest = Math.min(smallest, capacity);
}
return smallest;
}
public static void main(String[] args) {
long[] route = {1, 1, 2};
System.out.println(routeBottleneck(route));
}
}The printed value is 1. That means the route can add only 1 unit during the current pass, even though one edge on the route still has 2 units available. The bottleneck always comes from the smallest residual capacity on the route BFS found.
The total flow grows because every successful pass adds one bottleneck value from a source-to-sink route. The residual graph records what changed after that push, so the next BFS respects both the original capacity limits and the flow that has already been sent.
Java Implementation Walkthrough
The Java version follows the same sequence as the algorithm. We need a residual graph, a BFS pass that records how the sink was reached, and an augmenting pass that changes residual capacities before adding to the total flow. We keep those jobs separate so the graph storage, search step, update step, and cost analysis all have their own place.
Edge Model
The graph representation starts with an edge object that can point to its paired reverse edge. Edmonds-Karp needs that pair because every push changes two residual capacities at the same time. The forward edge loses capacity, while the reverse edge gains cancellation capacity.
We can model that residual edge with a small nested class:
private static final class Edge {
private final int to;
private final int reverse;
private long capacity;
private Edge(int to, int reverse, long capacity) {
this.to = to;
this.reverse = reverse;
this.capacity = capacity;
}
}The to field stores the destination vertex for this residual edge. The reverse field stores the index of the paired edge inside the destination vertex’s adjacency list. The capacity field stores the current residual capacity, so it changes as flow moves through the network.
An adjacency list fits this algorithm well because BFS needs to scan the outgoing residual edges from the current vertex. The constructor creates a list for every vertex, and addEdge creates the paired forward and backward residual edges:
import java.util.ArrayList;
import java.util.List;
public class EdmondsKarp {
private static final class Edge {
private final int to;
private final int reverse;
private long capacity;
private Edge(int to, int reverse, long capacity) {
this.to = to;
this.reverse = reverse;
this.capacity = capacity;
}
}
private final List<Edge>[] graph;
@SuppressWarnings("unchecked")
public EdmondsKarp(int vertices) {
if (vertices <= 0) {
throw new IllegalArgumentException();
}
graph = (List<Edge>[]) new ArrayList[vertices];
for (int vertex = 0; vertex < vertices; vertex++) {
graph[vertex] = new ArrayList<>();
}
}
public void addEdge(int from, int to, long capacity) {
checkVertex(from);
checkVertex(to);
if (capacity < 0) {
throw new IllegalArgumentException();
}
Edge forward = new Edge(to, graph[to].size(), capacity);
Edge backward = new Edge(from, graph[from].size(), 0);
graph[from].add(forward);
graph[to].add(backward);
}
private void checkVertex(int vertex) {
if (vertex < 0 || vertex >= graph.length) {
throw new IllegalArgumentException();
}
}
}The forward edge begins with the original capacity from the input. The backward edge begins with 0 because no flow has been sent yet, so nothing can be canceled at the start. When addEdge(0, 1, 3) runs, the adjacency list for vertex 0 receives a residual edge toward 1 with capacity 3, and the adjacency list for vertex 1 receives the paired reverse edge toward 0 with capacity 0.
The reverse index keeps residual updates direct. If the algorithm is changing the edge from 0 to 1, it can reach the paired edge from 1 to 0 by reading edge.reverse. That avoids scanning the neighbor list to find the matching reverse edge.
Capacities are stored as long in this version. That gives the code enough numeric range for typical learning and contest input. If a graph can produce total flow beyond Long.MAX_VALUE, the numeric type would need to change to something larger, such as BigInteger, with heavier arithmetic.
BFS Pass
Breadth-first search reads the current residual graph and finds the next source-to-sink route with the fewest edges. The search does not change capacities. It records how vertices were reached, so the augmenting step can trace the route backward from sink to source. Two parent arrays carry that route information. parentVertex[v] stores the vertex that reached v, while parentEdge[v] stores the edge index used from that parent. We mark the source as its own parent so BFS does not visit it again during the same search.
The BFS pass can be written as a helper method:
import java.util.ArrayDeque;
import java.util.Arrays;
private boolean bfs(int source, int sink, int[] parentVertex, int[] parentEdge) {
Arrays.fill(parentVertex, -1);
Arrays.fill(parentEdge, -1);
ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.add(source);
parentVertex[source] = source;
while (!queue.isEmpty()) {
int current = queue.remove();
for (int edgeIndex = 0; edgeIndex < graph[current].size(); edgeIndex++) {
Edge edge = graph[current].get(edgeIndex);
if (edge.capacity <= 0 || parentVertex[edge.to] != -1) {
continue;
}
parentVertex[edge.to] = current;
parentEdge[edge.to] = edgeIndex;
if (edge.to == sink) {
return true;
}
queue.add(edge.to);
}
}
return parentVertex[sink] != -1;
}The queue gives BFS its level-by-level scan. Vertices reached in fewer edges are processed before vertices farther away from the source. The first time BFS reaches the sink, the recorded parent arrays represent a shortest augmenting route by edge count.
The condition edge.capacity <= 0 blocks residual edges that cannot carry more flow in that direction. The condition parentVertex[edge.to] != -1 prevents revisiting a vertex during the same BFS pass. Those two checks keep the search limited to residual edges that can still carry more flow and vertices that have not already been reached.
When BFS returns true, the algorithm has enough parent data to rebuild the route. When it returns false, the sink cannot be reached through positive residual capacity, so the loop in maxFlow is done.
Augmenting Pass
After BFS finds a route, Edmonds-Karp walks backward from the sink to the source to find the bottleneck. The bottleneck is the smallest residual capacity on that route. The algorithm then walks backward again and applies that same amount to every edge on the route.
The maxFlow method ties the search and residual update steps into the main loop:
public long maxFlow(int source, int sink) {
checkVertex(source);
checkVertex(sink);
if (source == sink) {
throw new IllegalArgumentException();
}
long totalFlow = 0;
int[] parentVertex = new int[graph.length];
int[] parentEdge = new int[graph.length];
while (bfs(source, sink, parentVertex, parentEdge)) {
long bottleneck = Long.MAX_VALUE;
for (int vertex = sink; vertex != source; vertex = parentVertex[vertex]) {
Edge edge = graph[parentVertex[vertex]].get(parentEdge[vertex]);
bottleneck = Math.min(bottleneck, edge.capacity);
}
for (int vertex = sink; vertex != source; vertex = parentVertex[vertex]) {
Edge edge = graph[parentVertex[vertex]].get(parentEdge[vertex]);
edge.capacity -= bottleneck;
graph[edge.to].get(edge.reverse).capacity += bottleneck;
}
totalFlow += bottleneck;
}
return totalFlow;
}The first backward loop reads the route without changing the graph. It starts at the sink, jumps to the parent vertex recorded by BFS, and keeps going until it reaches the source. During that walk, it reads the residual capacity of every selected edge and keeps the smallest value as bottleneck.
The second backward loop performs the residual update. The line edge.capacity -= bottleneck reduces the remaining room in the chosen forward direction. The line graph[edge.to].get(edge.reverse).capacity += bottleneck records how much of that push can be canceled later through the paired reverse edge.
The total flow increases only after the full route has been updated. That order keeps the returned value aligned with the residual graph state. If BFS finds three augmenting routes with bottlenecks 2, 2, and 1, the final return value becomes 5.
This driver builds the four-vertex graph and prints the maximum flow value:
public static void main(String[] args) {
EdmondsKarp maxFlow = new EdmondsKarp(4);
maxFlow.addEdge(0, 1, 3);
maxFlow.addEdge(0, 2, 2);
maxFlow.addEdge(1, 2, 1);
maxFlow.addEdge(1, 3, 2);
maxFlow.addEdge(2, 3, 4);
System.out.println(maxFlow.maxFlow(0, 3));
}The output is 5. Source 0 can send 3 units through edge 0 -> 1 and 2 units through edge 0 -> 2. The residual updates let Edmonds-Karp build that total through repeated BFS passes instead of trying to fill the whole graph in a single move.
Complexity
Time cost is usually written as O(V * E^2), where V is the vertex count and E is the number of original directed edges. The residual graph stores a forward and reverse edge for every original edge, but 2E still counts as O(E) in Big O terms.
Every BFS pass scans adjacency lists and checks residual capacity, so a single BFS costs O(E). After BFS succeeds, the backward bottleneck walk and the backward update walk can each cross at most V - 1 edges, so those route walks cost O(V). In the full Edmonds-Karp bound, the BFS scan controls the per-pass cost, so a full augmenting pass is treated as O(E).
The number of augmenting passes is bounded by O(V * E). Multiplying that by the O(E) scan per pass gives the full time complexity of O(V * E^2).
Space complexity is O(V + E). The adjacency list array takes O(V), the stored residual edges take O(E), the BFS queue can hold up to O(V) vertices, and the parent arrays take O(V). Those parts combine into O(V + E) memory.
Conclusion
Edmonds-Karp builds maximum flow through a repeated cycle of BFS, bottleneck reading, and residual updates. We search the current residual graph for the shortest available route from source to sink, push only the smallest remaining capacity on that route, then reduce forward capacity while increasing reverse capacity for later cancellation. The total flow rises by that bottleneck after each successful pass, and the process stops when BFS can no longer reach the sink through positive residual capacity. That search, push, update, repeat flow is the core mechanic behind the Java version.
Thanks for reading! If you found this helpful, highlighting, clapping, or leaving a comment really helps me out.