12.5 Dinic's Algorithm

Edmonds-Karp guarantees polynomial running time, but it still performs only one augmentation per BFS search.

algorithmsgraphsnetwork-flow

12.5 Dinic's Algorithm

Problem

Edmonds-Karp guarantees polynomial running time, but it still performs only one augmentation per BFS search.

Consider a network containing thousands of shortest augmenting paths.

Edmonds-Karp may discover:

Path 1
augment

Path 2
augment

Path 3
augment

...

even though all paths belong to the same shortest-path structure.

The repeated BFS traversals become expensive.

We need an algorithm that can exploit many shortest augmenting paths at once.

Solution

Dinic's algorithm improves upon Edmonds-Karp by introducing two new ideas:

  1. Level graphs
  2. Blocking flows

Instead of augmenting one path at a time, Dinic pushes flow through an entire collection of shortest paths before rebuilding the residual graph.

This dramatically reduces the number of BFS phases.

The algorithm alternates between:

  1. Building a level graph using BFS.
  2. Finding a blocking flow using DFS.

This process continues until the sink becomes unreachable.

Level Graph

A level graph contains only edges that advance exactly one level away from the source.

Suppose BFS produces:

Vertex Distance
S 0
A 1
B 1
C 2
T 3

Valid level edges satisfy:

level(v) = level(u) + 1

For example:

S → A
S → B
A → C
B → C
C → T

are retained.

An edge such as:

C → A

is discarded because it moves backward.

The resulting graph becomes acyclic.

Example

Residual graph:

       A
     ↗   ↘
S             C → T
     ↘   ↗
       B

Levels:

S = 0
A = 1
B = 1
C = 2
T = 3

Level graph:

S → A
S → B
A → C
B → C
C → T

Every edge moves one level forward.

Blocking Flow

A blocking flow saturates enough edges that no further source-to-sink path remains in the level graph.

Important:

A blocking flow is not necessarily a maximum flow.

It only blocks all shortest augmenting paths.

After computing a blocking flow:

  • shortest paths disappear
  • sink becomes unreachable within the current level graph

A new BFS phase is then required.

Example

Consider:

       5
S → A → T

       7
S → B → T

Level graph contains two shortest paths:

S → A → T
S → B → T

Dinic pushes:

5

through the first path and:

7

through the second path during the same phase.

Total blocking flow:

12

Edmonds-Karp would require two separate augmentations.

High-Level Algorithm

Repeat:

  1. Build level graph using BFS.
  2. If sink unreachable, stop.
  3. Compute blocking flow.
  4. Update residual graph.

Return maximum flow.

BFS Phase

The BFS computes distance labels.

distance[source] = 0

Every reachable vertex receives:

distance[neighbor]
=
distance[current] + 1

Only shortest residual paths appear in the level graph.

Complexity:

O(E)

DFS Phase

After BFS, DFS sends flow through the level graph.

DFS respects levels:

level(next)
=
level(current) + 1

Backward movement is forbidden.

The DFS attempts to push as much flow as possible toward the sink.

When a path becomes saturated, DFS automatically explores alternatives.

Current Arc Optimization

A major optimization in Dinic is the current arc pointer.

Suppose DFS already determined:

A → X

cannot contribute additional flow.

Future DFS calls do not revisit that edge.

Each vertex remembers:

next unexplored edge

This prevents repeated scanning of dead edges.

Without this optimization, Dinic becomes significantly slower.

Detailed Example

Network:

S → A (10)
S → B (10)

A → C (5)
B → C (10)

C → T (15)

BFS

Levels:

Vertex Level
S 0
A 1
B 1
C 2
T 3

Level graph:

S → A
S → B
A → C
B → C
C → T

DFS

First path:

S → A → C → T

Bottleneck:

5

Push 5.

Second path:

S → B → C → T

Remaining bottleneck:

10

Push 10.

Blocking flow:

15

New Residual Graph

Edge:

C → T

becomes saturated.

No shortest path remains.

A new BFS phase begins.

In this example the maximum flow has already been reached.

Why Dinic Is Faster

Edmonds-Karp:

BFS
augment

BFS
augment

BFS
augment

Dinic:

BFS

many DFS augmentations

BFS

many DFS augmentations

Each BFS phase may eliminate a large number of shortest paths simultaneously.

This greatly reduces work.

Correctness

Two properties guarantee correctness.

Property 1

Every DFS augmentation preserves flow feasibility.

Capacity constraints remain satisfied.

Flow conservation remains satisfied.

Property 2

Every BFS phase increases the shortest-path distance from source to sink.

The sink moves farther away in the residual graph.

Eventually:

sink unreachable

At that moment no augmenting path exists.

Maximum flow has been reached.

Complexity Analysis

General Graphs

Using current arc optimization:

O(V²E)

This is already substantially better than Edmonds-Karp:

O(VE²)

for many graphs.

Unit Capacity Networks

When capacities are:

0 or 1

Dinic achieves:

O(E√V)

This is particularly important for matching problems.

Bipartite Matching

Hopcroft-Karp can be viewed as a specialized Dinic variant.

Its famous complexity:

O(E√V)

comes from the same shortest-path layering principle.

Implementation Structure

Typical edge structure:

Edge {
    to
    residual
    reverse
}

Algorithm:

while BFS():

    reset current pointers

    while DFS() pushes flow:

        add to answer

This pattern appears in most competitive programming and production implementations.

Common Mistakes

Ignoring Level Constraints

DFS must only follow:

level(next)
=
level(current) + 1

Violating this destroys correctness.

Forgetting Current Arc Optimization

The algorithm remains correct.

Performance degrades dramatically.

Reusing Old Levels

After a blocking flow completes, a new BFS must rebuild the level graph.

Old levels become invalid.

Not Updating Reverse Edges

Residual capacities must always satisfy:

forward -= pushed
reverse += pushed

Failing to update reverse edges corrupts the residual network.

Comparison

Algorithm Complexity
Ford-Fulkerson O(EF)
Edmonds-Karp O(VE²)
Dinic O(V²E)
Dinic (unit capacities) O(E√V)

Dinic is the standard maximum-flow algorithm for many practical applications because it combines strong theoretical guarantees with excellent real-world performance.

Applications

Dinic frequently appears in:

  • Maximum bipartite matching
  • Scheduling
  • Resource allocation
  • Project selection
  • Network routing
  • Competitive programming
  • Industrial optimization systems

Many problems with tens of thousands of vertices can be solved comfortably using Dinic.

Takeaway

Dinic's algorithm extends the shortest-path philosophy of Edmonds-Karp by processing entire layers of shortest augmenting paths at once. The level graph identifies all shortest routes from source to sink, while the blocking flow eliminates them in a single phase.

This combination reduces the number of BFS traversals dramatically and produces one of the most important maximum-flow algorithms ever developed. The next recipe introduces the push-relabel framework, a fundamentally different approach that abandons augmenting paths entirely and instead moves excess flow locally through the network.