Dinic's algorithm

The dinic's algorithm is an algorithm of the graph theory for determining a maximum flux in a network . It was developed by EA Dinic (Jefim (Chaim) Dinic) and published in 1970. It is a further development of the Edmonds-Karp algorithm , which Dinic developed independently of Jack Edmonds and Richard M. Karp . Dinic's algorithm differs from the Edmonds-Karp algorithm in that, in each pass, not only a single shortest st-path is augmented, but sometimes larger st-flows that are composed of several shortest st-paths.

The algorithm

In the following, the directional graph in the network , the capacity function ( indicating the capacity of an edge ), the node from which the flow starts, and the destination node of the flow. denotes the set of nodes of the graph and the set of edges. For a flow denotes the residual graph and the layer graph, i.e. the graph that shares with the set of nodes and consists of precisely those edges that belong to any node and to a shortest sv-path of . In particular, it also contains all edges that belong to a shortest st-path in . denotes the residual capacity belonging to the residual graph. A blocking flow (also called a blocking flow) in is an st-flow that utilizes at least one edge in every st-path . For an edge denotes the associated rear edge of the residual graph. ${\displaystyle (G,u,s,t)}$ ${\displaystyle G}$ ${\displaystyle u\colon E(G)\rightarrow \mathbb {R} _{+}}$ ${\displaystyle u(e)}$ ${\displaystyle e}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle V(G)}$ ${\displaystyle G}$ ${\displaystyle E(G)}$ ${\displaystyle f}$ ${\displaystyle G_{f}}$ ${\displaystyle G_{f}^{L}}$ ${\displaystyle G}$ ${\displaystyle (u,v)\in E(G_{f})}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G_{f}}$ ${\displaystyle G_{f}^{L}}$ ${\displaystyle G_{f}}$ ${\displaystyle u_{f}}$ ${\displaystyle G_{f}^{L}}$ ${\displaystyle G_{f}^{L}}$ ${\displaystyle e\in E(G)}$ ${\displaystyle {\overleftarrow {e}}}$

The algorithm works as follows:

1. Bet for each edge . ${\displaystyle f(e):=0}$ ${\displaystyle e\in E(G)}$
2. Determine the shift graph . ${\displaystyle G_{f}^{L}}$
3. Determine a blocking flow in . ${\displaystyle g}$ ${\displaystyle G_{f}^{L}}$
4. If the flow is zero, we're done, otherwise augment along (i.e. for each edge set: (with , if )) and jump to 2. ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle e\in E(G)}$ ${\displaystyle f(e):=f(e)+g(e)-g({\overleftarrow {e}})}$ ${\displaystyle g(e):=0}$ ${\displaystyle e\notin E(G_{f}^{L})}$

At the end there is a maximum st-flow, since there is no longer an st-path in the residual graph. ${\displaystyle f}$ ${\displaystyle G_{f}}$

Find blocking flow

Step 3 of the algorithm, a barrier can flow in for example be calculated as follows: ${\displaystyle g}$ ${\displaystyle G_{f}^{L}}$

1. Bet for each edge . ${\displaystyle g(e):=0}$ ${\displaystyle e\in G_{f}^{L}}$
2. Set . ${\displaystyle H:=G_{f}^{L}}$
3. BEGIN
   • ${\displaystyle P:=[s]}$ (Way out of only one knot without edges)
   • ${\displaystyle v:=s}$
   • jump to FORWARD.
4. IN FRONT
   • If no edge leaves the knot , jump to BACK. ${\displaystyle H}$ ${\displaystyle v}$
   • Otherwise
     • Select an edge from . ${\displaystyle (v,w)}$ ${\displaystyle H}$
     • Extend at . ${\displaystyle P}$ ${\displaystyle (v,w)}$
     • ${\displaystyle v:=w}$
     • If so , go to FORWARD. ${\displaystyle v\neq t}$
     • If so , skip to AUGMENT. ${\displaystyle v=t}$
5. AUGMENT
   • Augmentiere along as much as possible (i. E. For set for each ). ${\displaystyle g}$ ${\displaystyle P}$ ${\displaystyle \gamma :=\min _{e\in E(P)}u_{f}(e)}$ ${\displaystyle g(e):=g(e)+\gamma \!\,}$ ${\displaystyle e\in E(P)}$
   • Remove the edges that are being busy. ${\displaystyle H}$
   • Jump to START.
6. BACK
   • If so, the flow is blocked, i.e. STOP. ${\displaystyle v=s}$ ${\displaystyle g}$
   • Otherwise
     • Be last edge on . ${\displaystyle (u,v)}$ ${\displaystyle P}$
     • Shorten by . ${\displaystyle P}$ ${\displaystyle (u,v)}$
     • Remove and remove any edges that may be incident with it . ${\displaystyle v}$ ${\displaystyle H}$
     • ${\displaystyle v:=u}$
     • Jump to FORWARD.

At the end of this procedure, lock flow is in . Be and . This method requires a running time of to calculate a blocking flow . Because every call of AUGMENTATE requires runtime and each of these calls takes an edge from the graph, so there are at most these calls (because the layer graph has at most edges). Because the layer graph does not contain any directed circles, each node can be reached at most once by a VOR operation between two AUGMENTATION calls, so a maximum of these are carried out in total ; a VOR operation can be executed in constant runtime. In the BACK operations, a node is removed each time, so they are performed at most two times, all BACK operations together have a running time of . ${\displaystyle g}$ ${\displaystyle G_{f}^{L}}$ ${\displaystyle m=|E(G)|}$ ${\displaystyle n=|V(G)|}$ ${\displaystyle {\mathcal {O}}(nm)}$ ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle m}$ ${\displaystyle G_{f}^{L}}$ ${\displaystyle m}$ ${\displaystyle G_{f}^{L}}$ ${\displaystyle {\mathcal {O}}(nm)}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {O}}(n+m)}$

annotation

Instead of the layer graph, EA Dinic worked with a subgraph that consists precisely of the nodes and edges that lie on the shortest st paths. The use of the layer graph works in the same way, but simplifies the description of the algorithm.

running time

Be and . Dinic's algorithm requires at most passes. The layer graph can be calculated in runtime using breadth-first search . A blocking flow in can be calculated in runtime using the method given above . This results in a total running time of . This is also the running time, which was proven by Dinic in 1970. However, the Goldberg-Tarjan algorithm works faster. ${\displaystyle m=|E(G)|}$ ${\displaystyle n=|V(G)|}$ ${\displaystyle n-1}$ ${\displaystyle G_{f}^{L}}$ ${\displaystyle {\mathcal {O}}(m)}$ ${\displaystyle G_{f}^{L}}$ ${\displaystyle {\mathcal {O}}(nm)}$ ${\displaystyle {\mathcal {O}}(n^{2}m)}$

With an improvement by Alexander Karzanov from 1974, a running time of can also be achieved for the Dinic algorithm . ${\displaystyle {\mathcal {O}}(n^{3}+nm)}$

swell

• Bernhard Korte , Jens Vygen : Combinatorial Optimization: Theory and Algorithms . Translated from the English by Rabe von Randow. Springer-Verlag, Berlin Heidelberg 2008, ISBN 978-3-540-76918-7
• Helmut Alt: Lecture notes for higher algorithms , winter semester 2006/2007, Free University of Berlin. (PDF; 2.5 MB)

Web links

• EA Dinic: Algorithm for solution of a problem of maximum flow in a network with power estimaton , 1970 (PDF; 428 kB) - EA Dinics publication of the algorithm