Dinic algorithm

Dinic algorithm

The Dinic or Dinitz algorithm is based on two concepts: a level graph, and a blocking flow (level graph & blocking flow).

To determine the level graph, we place the source at level 1, its successors at level 2, and so on.

Dinic algorithm

The blocking flow is the maximum flow that can pass in a given path.

Dinic algorithm

Dinic's algorithm is as follows:

  1. build a level graph
  2. find an increasing path (the smallest) from the source to the well
  3. find the arc limiting the increasing path
  4. find a path increasing from limiting summit to the well
  5. repeat steps 3 and 4 to build a blocking flow until there is no longer an increasing path

Example

Construction of the level graph:

Dinic algorithm

Find an increasing path, find the limiting arc:

Dinic algorithm

Return to step 3 and 4:

Dinic algorithm

And so on until no longer finding an increasing path:

Dinic algorithm
To share
en_GBEN
%d bloggers like this: