FANDOM


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:

  1. Flow on an edge doesn't exceed the given capacity on that edge.
  2. 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.

Algorithm Edit

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.

Algorithm:

  1. Build a level graph (assigning levels to vertices) by doing BFS of G
  2. Find an augmenting path from source to sink
  3. Find the bottleneck on augmenting path
  4. Find the augmenting path from bottleneck to sink
  5. Repeat step 3 and step 4 to construct a blocking flow until no augmenting path found

See Also Edit