Algorithme de Dinic

Soit ${\displaystyle G=((V,E),c,s,t)}$ un réseau; ${\displaystyle c(u,v)}$ et ${\displaystyle f(u,v)}$ dénotent respectivement la capacité et le flot sur un arc ${\displaystyle (u,v)}$.

La capacité résiduelle est l’application ${\displaystyle c_{f}:V\times V\to R^{+}}$ définie comme suit :

• si ${\displaystyle (u,v)\in E}$,

  ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$,

  ${\displaystyle c_{f}(v,u)=f(u,v)}$,

• ${\displaystyle c_{f}(u,v)=0}$ sinon.

Le graphe résiduel est le graphe ${\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}$, où

${\displaystyle E_{f}=\{(u,v)\in V\times V:c_{f}(u,v)>0\}}$.

Un chemin augmentant est un chemin de la source ${\displaystyle s}$ au puits ${\displaystyle t}$ (on dit aussi un ${\displaystyle s}$-${\displaystyle t}$-chemin) dans le graphe résiduel. On note ${\displaystyle d(v)}$ la longueur des plus courts chemins de la source ${\displaystyle s}$ au sommet ${\displaystyle v}$ dans ${\displaystyle G_{f}}$ (${\displaystyle d(v)}$ est la distance de la source à ${\displaystyle v}$).

Le graphe de niveau de ${\displaystyle G_{f}}$ est le graphe ${\displaystyle G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)}$, où

${\displaystyle E_{L}=\{(u,v)\in E_{f}:d(v)=d(u)+1\}}$.

En d'autres termes, c'est le sous-graphe contenant uniquement les arcs qui relient un sommet à un sommet de distance immédiatement supérieure.

Un flot bloquant est un flot ${\displaystyle f}$ tel que le graphe ${\displaystyle G'=(V,E_{L}',s,t)}$ avec ${\displaystyle E_{L}'=\{(u,v):f(u,v)<c_{f}|_{E_{L}}(u,v)\}}$ obtenu en ne conservant que les arcs sur lesquels le flot ${\displaystyle f}$ est strictement inférieur à la capacité ${\displaystyle c_{f}|_{E_{L}}}$ ne contient aucun ${\displaystyle s}$-${\displaystyle t}$-chemin. Autrement dit, un flot est bloquant si tout ${\displaystyle s}$-${\displaystyle t}$-chemin contient un arc où le flot est égal à la capacité.

Algorithme de Dinic

Entrée: Un réseau ${\displaystyle G=((V,E),c,s,t)}$.

Sortie: Un flot ${\displaystyle f}$ de valeur maximale.

1. Poser ${\displaystyle f(u,v)=0}$ pour tout ${\displaystyle (u,v)\in E}$.
2. Construire le graphe de niveau ${\displaystyle G_{L}}$ de ${\displaystyle G_{f}}$ à partir de ${\displaystyle G}$. Si le puits n'est pas accessible, terminer et retourner le flot ${\displaystyle f}$.
3. Déterminer un flot bloquant ${\displaystyle f\;'}$ dans ${\displaystyle G_{L}}$.
4. Augmenter le flot ${\displaystyle \ f}$ de ${\displaystyle f\;'}$ et retourner au point 2.

L'exemple suivant montre l'exécution de l'algorithme de Dinic. Dans le graphe de niveau ${\displaystyle G_{L}}$ les valeurs en rouge sont les distances à la source, les arcs en bleu forment un flot bloquant.

	${\displaystyle G}$	${\displaystyle G_{f}}$	${\displaystyle G_{L}}$
1.
	Au départ, le flot est nul, donc ${\displaystyle G_{f}=G}$. Le flot bloquant obtenu à la fin de la première étape a pour valeur 14. Il est composé de trois chemins augmentant, tous de longueur 3. Ce sont ${\displaystyle \{s,1,3,t\}}$ avec valeur 4, ${\displaystyle \{s,1,4,t\}}$ avec valeur 6, ${\displaystyle \{s,2,4,t\}}$ avec valeur 4.
2.
	Le graphe résiduel ${\displaystyle G_{f}}$ a des arcs opposés à ceux du graphe de départ, notamment lorsque la capacité est égale au flot. Les distances ne sont plus les mêmes. Le flot bloquant a pour valeur 5. Il correspond au chemin seul augmentant ${\displaystyle \{s,2,4,3,t\}}$ avec valeur 5. La valeur du flot devient 14 + 5 = 19. Le chemin augmentant est composé de 4 arcs.
3.
	Le sommet ${\displaystyle t}$ n'est plus accessible dans ${\displaystyle G_{f}}$. L'algorithme se termine et retourne un flot dont la valeur est 19. Notons que dans chaque flot bloquant, le nombre d'arcs du chemin augmentant croît d'au moins 1.

• Algorithme de Ford-Fulkerson
• Problème de flot maximum

• E. A. Dinic, « Algorithm for solution of a problem of maximum flow in a network with power estimation », Soviet Math. Doklady, Doklady Nauk SSSR, vol. 11,‎ 1970, p. 1277–1280 (lire en ligne). Traduction anglaise de l’article russe paru la même année.
• Yefim Dinitz, « Dinitz' Algorithm: The Original Version and Even's Version », dans Oded Goldreich, Arnold L. Rosenberg et Alan L. Selman, Theoretical Computer Science: Essays in Memory of Shimon Even, Springer, 2006 (ISBN 978-3-540-32880-3, lire en ligne), p. 218–240
• Robert E. Tarjan, Data structures and network algorithms, 1983
• (en) Bernard H. Korte et Jens Vygen, Combinatorial Optimization : Theory and Algorithms, Springer, coll. « Algorithms and Combinatorics » (n^o 21), 2008, 627 p. (ISBN 978-3-540-71844-4), « 8.4 Blocking Flows and Fujishige's Algorithm », p. 174–176

Traduction française:

• Bernard Korte, Jens Vygen et Jean Fonlupt et Alexandre Skoda (traducteurs), Optimisation combinatoire : théorie et algorithmes, Springer-France, coll. « IRIS », 2010 (ISBN 978-2-287-99036-6), « 8.4 Flots bloquants et algorithme de Fujishige », p. 180–182
• (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, Cambridge, MIT Press and McGraw-Hill, 2001, 2^e éd., 1180 p. (ISBN 978-0-262-53196-2, LCCN 2001031277), chap. 26 (« Chap. 26 Flows »), p. 643–700. Traduction française : Introduction à l'algorithmique, 2^e édition, Dunod 2002, « chapitre 26. Flot Maximum ».