Dinic's Algorithm

@dinics_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.

Pseudo-code
function dinic(g, s, t):
    f <- 0

    while bfs_level_graph(g, s, t):
        initialize ptr array to 0

        while true:
            pushed <- dfs_send_flow(s, t, INF)
            if pushed == 0 then
                break
            f <- f + pushed

    return f

function bfs_level_graph(g, s, t):
    initialize level array with -1
    level[s] <- 0
    create queue and push s

    while queue not empty:
        v <- pop from queue
        for each edge (v -> to):
            if level[to] == -1 and capacity > flow:
                level[to] <- level[v] + 1
                push to into queue

    return level[t] != -1

function dfs_send_flow(v, t, pushed):
    if pushed == 0 then
        return 0
    if v == t then
        return pushed

    for each edge starting from ptr[v]:
        to <- edge destination

        if level[to] != level[v] + 1 or capacity <= flow:
            continue

        tr <- dfs_send_flow(to, t, min(pushed, capacity - flow))

        if tr == 0 then
            continue

        update flow on edge and reverse edge
        return tr

    return 0
  • s s is the source node where all flow starts, like a water tank.
  • t t is the sink node where flow ends, like the destination.
  • g g is the graph representing the network of pipes and their capacities.
  • f f is the total flow we have sent so far from s to t.
  • residual_graph residual_graph shows how much capacity is still left in each edge after sending flow.
  • level level stores the distance (in edges) from the source to each node, used to build layers.
  • ptr ptr remembers which edges we have already tried for each node to avoid repeating work.
  • v v is the current node we are exploring.
  • cap cap is the maximum capacity of an edge.
  • flow flow is how much flow is currently passing through an edge.
  • 0 0 means no flow at the beginning.
  • INF INF represents a very large value when we try to push as much flow as possible.
Recipe Steps
1

Imagine a system of pipes. First, group pipes into layers based on how far they are from the source. This is like organizing roads by distance from your house.

2

Only allow water to move forward layer by layer. This prevents going in circles and wasting time.

3

Now try to push as much water as possible from the source to the sink using these layers. This is like sending water through all possible shortest routes.

4

Whenever a path gets full, stop using it and try another path in the same layer structure.

5

When no more water can flow in this layered setup, rebuild the layers again using updated capacities.

6

Repeat building layers and sending flow until no path from source to sink exists.

7

The total water sent at the end is the maximum flow.

Questions & Answers

It sends multiple flows in one BFS phase using DFS instead of only one path at a time.

It is a layered version of the graph where each node has a distance from the source.

BFS builds structure, and DFS uses that structure to efficiently push flow.

When BFS can no longer reach the sink from the source.
- Dinic's algorithm works in phases, each starting with a BFS.
- The BFS creates layers that guide the flow direction.
- DFS is used to push flow efficiently through these layers.
- Edges that are full are skipped to avoid unnecessary work.
- The algorithm is much faster than simpler max-flow methods in many cases.
- Rebuilding layers is necessary after each phase because capacities change.

Related Algorithms
Edmonds-Karp 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.

View
Kruskal's Algorithm

Kruskal's Algorithm finds a Minimum Spanning Tree (MST) by always picking the smallest edge that does not form a cycle, until all nodes are connected.

View
Prim’s Algorithm

Prim’s Algorithm builds a Minimum Spanning Tree (MST) by starting from one node and growing the tree step by step, always adding the smallest edge that connects a new node.

View