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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.