Contents
ToggleDinic algorithm
The Dinic or Dinitz algorithm is based on two notions: a graph level, 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 Dinic Algorithm dinic algorithm dinitz level graph](https://complex-systems-ai.com/wp-content/uploads/2016/05/dinic1.png)
The blocking flow is the maximum flow can pass in a given path.
![Dinic Algorithm Dinic Algorithm dinic algorithm dinitz level graph](https://complex-systems-ai.com/wp-content/uploads/2016/05/dinic2.png)
Dinic's algorithm is as follows:
- build a level graph
- find an increasing path (the smallest) from the source to the well
- find the arc limiting the increasing path
- find a path increasing from limiting summit to the well
- 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 Dinic Algorithm dinic algorithm dinitz level graph](https://complex-systems-ai.com/wp-content/uploads/2016/05/dinic3.png)
Find an increasing path, find the limiting arc:
![Dinic Algorithm Dinic Algorithm dinic algorithm dinitz level graph](https://complex-systems-ai.com/wp-content/uploads/2016/05/dinic5.png)
Return to step 3 and 4:
![Dinic Algorithm Dinic Algorithm dinic algorithm dinitz level graph](https://complex-systems-ai.com/wp-content/uploads/2016/05/dinic6.png)
And so on until no longer finding an increasing path:
![Dinic Algorithm Dinic Algorithm dinic algorithm dinitz level graph](https://complex-systems-ai.com/wp-content/uploads/2016/05/dinic7.png)