I am learning Dinic algorithm from max-flow here.I am not able to understand the terms Level graph and blocking flow any one help me.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | maspy | 150 |
| 3 | Um_nik | 146 |
| 4 | Errichto | 139 |
| 5 | nik_exists | 138 |
| 6 | adamant | 136 |
| 7 | maroonrk | 134 |
| 8 | DNR | 133 |
| 9 | Dominater069 | 131 |
| 9 | AmShZ | 131 |
| Название |
|---|



This explains it nicely — http://www.slideshare.net/KuoE0/acmicpc-dinics-algorithm.
Level graph is just a BFS ordering of the nodes of the graph.
Blocking flow is adding a flow equal to the smallest possible flow value in the augmenting path and subtracting that flow from all the edges of that residual path.
Roughly explained,
Blocking flow in a certain graph is a flow that can't be increased by finding an augmenting path. Of course in general graphs that include reverse edges the blocking flow is maximum, but in Dinic's case we're finding a blocking flow in the level graph.
Level graph is a graph created by BFS from a source vertex, such that every edge A->B exists in the level graph if it exists in the original graph and the shortest distance from source to A is 1 less than the shortest distance from source to B. The graph is called 'level' graph because you can imagine the vertices ordered in levels by the distance from the source. What is important in this graph is the fact that since we use BFS to construct it, every path is a shortest path, which is good property when choosing augmenting paths.