Dinic's algorithm

The algorithm is an algorithm of Dinic from graph theory to determine a maximal flow over a network. It was developed by EA Dinic ( Yefim ( Chaim ) Dinic ) and published in 1970. It is a further development of the Edmonds - Karp algorithm, the Dinic developed independently by Jack Edmonds and Richard M. Karp. The algorithm of Dinic differs from the Edmonds - Karp algorithm by augmented in each pass not only to a single shortest st- path, but sometimes in larger st- flows that are composed of multiple shortest st- paths.

The algorithm

Hereinafter referred to the network the directed graph, the capacity function ( the capacitance indicates an edge ), the node, from which the flow starts, and the destination node of the river. denotes the set of nodes of the graph and the edge set. At a flow denotes the Residualgraphen and the layer graph, so the graph is divided with the set of nodes and consists of exactly the edges that belong to any node and a shortest sv- path from. In particular, also includes all of the edges belonging to a shortest path in st. denotes the belonging to Residualgraph residual capacity. (Also called blocking flow ) A blocking flow in a st- flow that auslastet in each st- path in at least one edge. For an edge denotes the associated trailing edge of the Residualgraphen.

The algorithm works as follows:

At the end is a maximum st- flow, since there is no st- path more in Residualgraphen.

Find blocking flow

For Step 3 of the algorithm, a blocking flow in, for example, can be calculated as follows:

  • (Path from one node without edges)
  • Jump to VOR.
  • If leaving the node in no edge, jump to RETURN.
  • Otherwise Choose from an edge.
  • Extend to.
  • If then go to the VOR.
  • If, jump to augment.
  • Augmentiere along as much as possible (ie, for each set ).
  • Removed from the edges to be utilized thereby.
  • Jump to START.
  • If, blocking flow, so STOP.
  • Otherwise Be final edge.
  • Shorten order.
  • Remove and all incident edges from him.
  • Jump to VOR.

At the end of this process is in reverse flow. Be and. This process requires a period of for the calculation of a blocking flow. For each call to augment requires maturity and each of these calls takes an edge from the graph, so there are at most of these calls (for the layer graph has at most edges). Because of the layer graph contains no directed cycles, two augment calls between each node can be reached at most once by a VOR operation, a maximum total of those are carried out; VOR operation can be performed in constant maturity. In the BACK operations at each time a node is removed, so they are at most times performed all BACK operations together have a term of.

Note

EA Dinic worked instead with the layered graph with a subgraph that consists exactly of the nodes and edges that lie on the shortest st- paths. The use of the layered graph works similarly, but simplifies the description of the algorithm.

Term

Be and. The algorithm uses at most of Dinic runs. The graph layer can be calculated using breadth-first search in run time. A barrier river can be calculated using the above method in runtime. This gives a total running time of. This is also the period, which was proved by Dinic 1970. However, the Goldberg - Tarjan algorithm works faster.

With an improvement of Alexander Karzanov 1974 can be achieved and a runtime of the algorithm of Dinic.

Swell

  • Bernhard Korte, Jens Vygen: Combinatorial Optimization: Theory and Algorithms. Translated from English by Rabe von Randow. Springer -Verlag, Berlin Heidelberg 2008, ISBN 978-3-540-76918-7
  • Helmut Alt: Lecture Notes Higher Algorithms, Winter Term 2006/2007, Free University of Berlin. (PDF, 2.5 MB)
Edmonds–Karp algorithm
48737
de