It is a Network Flow Algorithm. This Algorithm finds Max Flow from source 's' to sink 't' for a graph G where the edge capacities of every edge are known in O(V2E) time. Max flow has the following constraints:
- Flow on an edge doesn't exceed the given capacity on that edge.
- Incoming flow is equal to outgoing flow on every edge except s and t.
A flow is a Blocking Flow if no more flow can be sent using the level graph.
Theorem: f is a max flow after at most n-1 blocking flow computations.In Dinic's Algorithm, we use BFS to check if more flow is possible and also to construct a level graph. In Level Graph, we assign levels to all nodes. Level of a node is the shortest distance in terms of number of edges from source to that node. Once the level graph is constructed, we send multiple flows using this level graph.
- Build a level graph (assigning levels to vertices) by doing BFS of G
- Find an augmenting path from source to sink
- Find the bottleneck on augmenting path
- Find the augmenting path from bottleneck to sink
- Repeat step 3 and step 4 to construct a blocking ﬂow until no augmenting path found