Voir la source de Algorithme de Dinic

L{{'}}'''algorithme de Dinic''' ou '''algorithme de Dinitz''' est un algorithme en [[complexité en temps|temps polynomial]] (et même fortement polynomial<ref>Un algorithme est en temps ''fortement polynomial si le nombre d'opérations arithmétiques est polynomial, et si de plus la place prise pour représenter les calculs intermédiaire est polynomial en fonction de la taille 'ou du nombre) des nombres données en entrée. Voir par exemple {{harv|Korte|Vygen|2008|p=6}}.</ref>) de calcul du [[Problème de flot maximum|flot maximum]] dans un réseau, publié en 1970 par Yefim Dinitz<ref>{{harvsp|Dinic|1970}}.</ref>.
Le temps de calcul est en <math>O(|V|^2 |E|)</math> pour un graphe dont <math>V</math> est l'ensemble des sommets et <math>E</math> l’ensemble des arcs. Il est semblable à l'[[algorithme d'Edmonds-Karp]] dont le temps d'exécution est en <math>O(|V||E|^2)</math>. Comme lui, il utilise des chemins augmentants de longueur minimale. L'introduction des concepts de graphe de niveau et de flot bloquant permet d'obtenir cette meilleure performance.

== Définitions ==
Soit <math>G = ((V,E),c,s,t)</math> un réseau; <math>c(u,v)</math> et <math>f(u,v)</math> dénotent respectivement la capacité et le flot sur un arc <math>(u,v)</math>.

La '''capacité résiduelle''' est l’application <math>c_f : V\times V \to R^+</math> définie comme suit :
* si <math>(u,v)\in E</math>,
*: <math>c_f(u,v) = c(u,v) - f(u,v) </math>,
*: <math>c_f(v,u) = f(u,v)</math>,
* <math>c_f(u,v) = 0</math> sinon.

Le '''graphe résiduel''' est le graphe <math>G_f = ((V, E_f), c_f|_{E_f}, s, t)</math>, où
: <math>E_f = \{(u,v)\in V \times V : c_f(u,v) > 0\}</math>.

Un '''chemin augmentant''' est un chemin de la source <math>s</math> au puits <math>t</math> (on dit aussi un <math>s</math>-<math>t</math>-chemin) dans le graphe résiduel. On note <math>d(v)</math> la longueur des plus courts chemins de la source <math>s</math> au sommet <math>v</math> dans <math>G_f</math> (<math>d(v)</math> est la ''distance'' de la source à <math>v</math>).

Le '''graphe de niveau''' de <math>G_f</math> est le graphe <math>G_L = (V, E_L, c_f|_{E_L}, s,t)</math>, où
: <math>E_L = \{(u,v)\in E_f : d(v) = d(u) + 1\}</math>.
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 <math>f</math> tel que le graphe <math>G' = (V,E_L', s, t)</math> avec <math>E_L' = \{(u,v) : f(u,v) < c_f|_{E_L}(u,v)\}</math> obtenu en ne conservant que les arcs sur lesquels le flot <math>f</math> est strictement inférieur à la capacité <math>c_f|_{E_L}</math> ne contient aucun <math>s</math>-<math>t</math>-chemin. Autrement dit, un flot est bloquant si tout <math>s</math>-<math>t</math>-chemin contient un arc où le flot est égal à la capacité.

== L'Algorithme ==
'''Algorithme de Dinic'''
: ''Entrée'': Un réseau <math>G = ((V, E), c, s, t)</math>.
: ''Sortie'': Un flot <math>f</math> de valeur maximale.
# Poser <math>f(u,v) = 0</math> pour tout <math>(u,v)\in E</math>.
# Construire le graphe de niveau <math>G_L</math> de <math>G_f</math> à partir de <math>G</math>. Si le puits n'est pas accessible, terminer et retourner le flot <math>f</math>.
# Déterminer un flot bloquant <math>f\;'</math> dans <math>G_L</math>.
# Augmenter le flot <math>\ f</math> de <math>f\;'</math> et retourner au point 2.

== Exemple ==
L'exemple suivant montre l'exécution de l'algorithme de Dinic. Dans le graphe de niveau <math>G_L</math> les valeurs en rouge sont les distances à la source, les arcs en bleu forment un flot bloquant.

:{| class="wikitable" style="text-align:center; width:800px;" border="1"
|-
! width="15px" |

! <math>G</math>
! <math>G_f</math>
! <math>G_L</math>
|-
! 1.
| [[Fichier:Dinic algorithm G1.svg|250px]]
| [[Fichier:Dinic algorithm Gf1.svg|250px]]
| [[Fichier:Dinic algorithm GL1.svg|250px]]
|-
|
| align="left" colspan="3" |
Au départ, le flot est nul, donc <math>G_f=G</math>. 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
# <math>\{s, 1, 3, t\}</math> avec valeur 4,
# <math>\{s, 1, 4, t\}</math> avec valeur 6,
# <math>\{s, 2, 4, t\}</math> avec valeur 4.

|-
! 2.
| [[Fichier:Dinic algorithm G2.svg|250px]]
| [[Fichier:Dinic algorithm Gf2.svg|250px]]
| [[Fichier:Dinic algorithm GL2.svg|250px]]
|-
|
| align="left" colspan="3" |
Le graphe résiduel <math>G_f</math> 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
# <math>\{s, 2, 4, 3, t\}</math> avec valeur 5.
La valeur du flot devient 14 + 5 = 19. Le chemin augmentant est composé de 4 arcs.
|-
! 3.
| [[Fichier:Dinic algorithm G3.svg|250px]]
| [[Fichier:Dinic algorithm Gf3.svg|250px]]
| [[Fichier:Dinic algorithm GL3.svg|250px]]
|-
|
| align="left" colspan="3" |
Le sommet <math>t</math> n'est plus accessible dans <math>G_f</math>. 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.
|-
|}

== Analyse ==

=== Cas général ===
On peut montrer que le nombre d'arcs dans chaque flot bloquant croit d'au moins 1 à chaque étape; il y a donc au plus <math>n-1</math> étapes, et au plus <math>n-1</math> flots bloquants à calculer, où <math>n</math> est le nombre de sommets du réseau.

Le graphe de niveau <math>G_L</math> peut être calculé par un [[Algorithme de parcours en largeur|parcours en largeur]]; un tel parcours prend un temps en <math>O(m)</math>, où <math>m</math> est le nombre d'arcs. Un flot bloquant peut être calculé en temps <math>O(nm)</math> . Le temps total de l'algorithme de Dinic est donc en <math>O(n^2 m)</math>.

On peut diminuer le temps de calcul d'un flot bloquant en utilisant une structure de données de la famille des ''arbres dynamiques'', soit les arbres adaptatifs (self-adjusting trees) soit les {{Lien|langue=en|trad=link/cut tree|fr=link/cut tree|texte=link/cut tree}}, inventés par Sleator et [[Robert Tarjan|Tarjan]]. La détermination du flot bloquant de chaque étape peut être ramenée à <math>O(m \log n)</math>, et le temps total à <math>O(nm \log n)</math>.

=== Cas particuliers ===

'''Capacités 0 ou 1'''. Dans un réseau où les capacités sont 0 ou 1, la complexité en temps peut être nettement mieux bornée. Chaque flot bloquant peut être trouvé en temps <math>O(m)</math>, et on peut montrer que, de plus, le nombre d'étapes est majoré par <math>O(\sqrt{m})</math> et <math>O(n^{2/3})</math>. L'algorithme est donc en temps <math>O(\min(n^{2/3}, m^{1/2})m)</math>.

'''Réseaux de couplages'''. Dans les réseaux qui interviennent dans la résolution du [[couplage (théorie des graphes)|couplage biparti]], le nombre de phases est borné par <math>O(\sqrt{n})</math>, ce qui donne un temps borné par <math>O(\sqrt{n} m)</math>. L'algorithme est aussi connu sous le nom d'[[algorithme de Hopcroft-Karp]].

'''Réseaux unitaires'''. Plus généralement, cette borne reste valable pour des réseaux dits ''unitaires'', qui sont des réseaux où chaque sommet autre que la source et le puits possèdent soit un arc entrant de capacité un, soit un arc sortant de capacité un, les autres arcs ayant des capacités qui sont des entiers arbitraires{{sfn|Tarjan|1983|p=102}}.

== Historique ==
=== ''Dinic'' ou ''Dinitz'' ? ===
L'algorithme de Dinic a été publié en 1970 par Yefim (Chaim) A. Dinitz (Ефим Диниц), alors qu'il était en Russie. Comme le dit Dinitz dans son article historique en hommage au mathématicien et informaticien [[Shimon Even]], le [[rideau de fer]] séparait alors efficacement les chercheurs soviétiques des autres; son algorithme a été traduit dans la même année, et dans cette traduction, la lettre finale de son nom est remplacée par un « c ». C'est Shimon Even et Alon Itai, alors élève d'Even, qui ont découvert la traduction assez obscure de l'article, lui ont apporté des modifications et compléments, et en ont répandu la connaissance dans le monde scientifique occidental. Dinitz dit que l'algorithme ainsi reformulé - et qui circule encore aujourd'hui sous le nom d'algorithme de ''Dinic'' - doit son succès à Even et Atai, et que son algorithme original, algorithme de ''Dinitz'', n'aurait peut-être pas eu ce succès. L'algorithme continue à être appelé algorithme de ''Dinic'' dans les ouvrages de référence<ref>Par exemple dans {{harvsp|Cormen|Leiserson|Rivest|Stein|2001}}.</ref>, et par Dinitz lui-même, sur un ton amusé<ref>{{harvsp|Dinitz|2006}}.</ref>. Dinitz est maintenant membre du département d'informatique de l’[[université Ben Gourion du Néguev]] en Israël<ref>[http://www.cs.bgu.ac.il/~dinitz/ Page personnelle] de Dinitz à l'université Ben Gourion. </ref>. Ses publications scientifiques paraissent toujours sous son vrai nom.

=== Dinic et Edmonds-Karp ===
Deux ans plus tard, en 1972, paraît l'[[algorithme d'Edmonds-Karp]] mais qui avait déjà été présenté plus tôt<ref>L'article {{harv|Dinitz|2006}} contient une longue description des progrès successifs dans les algorithmes de flot maximum.</ref>. Ils ont montré indépendamment que si l'on choisit comme chemin augmentant le plus court à chaque pas, alors la longueur des chemins augmentant est croissante au sens large. L'algorithme est moins efficace que celui de Dinic parce qu'il ne fait pas usage de la notion de distance. Il avait déjà été présenté à une conférence aux États-Unis en 1968 (donc avant la publication de l'article de Dinic), mais pas publié à l'époque.

== Articles connexes ==
* [[Algorithme de Ford-Fulkerson]]
* [[Problème de flot maximum]]

== Notes ==
{{Références}}

== Bibliographie ==
* {{Article |prénom=E. A. |nom=Dinic |titre=Algorithm for solution of a problem of maximum flow in a network with power estimation |journal=Soviet Math. Doklady |volume=11 |numéro= |pages=1277–1280 |éditeur=Doklady Nauk SSSR |année=1970 |url= http://www.cs.bgu.ac.il/~dinitz/D70.pdf}}. Traduction anglaise de l’article russe paru la même année.
* {{chapitre | prénom = Yefim | nom= Dinitz | auteurs ouvrage =  Oded Goldreich, [[Arnold  L. Rosenberg]] et Alan L. Selman | titre ouvrage= Theoretical Computer Science: Essays in Memory of Shimon Even | titre chapitre = Dinitz' Algorithm: The Original Version and Even's Version | année = 2006 | éditeur = Springer | isbn = 978-3-540-32880-3 | passage = 218–240 | url = http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf}}
* {{ouvrage | nom=Tarjan | prénom=Robert E. |année =1983 | titre=Data structures and network algorithms }}
* {{Ouvrage | langue=en | prénom1=Bernard H. | nom1=Korte | prénom2=Jens | nom2=Vygen | titre=Combinatorial Optimization | sous-titre=Theory and Algorithms | éditeur=Springer | collection=Algorithms and Combinatorics | numéro dans collection=21 | année=2008 | pages totales=627 | isbn=978-3-540-71844-4 | titre chapitre=8.4 Blocking Flows and Fujishige's Algorithm | passage=174–176}}
Traduction française:
* {{Ouvrage | langue=fr | prénom1=Bernard | nom1=Korte | prénom2=Jens | nom2=Vygen | auteur3=Jean Fonlupt et Alexandre Skoda | responsabilité3=traducteurs | titre=Optimisation combinatoire | sous-titre=théorie et algorithmes | éditeur=Springer-France | collection=IRIS | année=2010 | pages totales= | isbn=978-2-287-99036-6 | titre chapitre=8.4 Flots bloquants et algorithme de Fujishige | passage=180–182}}
* {{Ouvrage|langue=en|prénom1=Thomas H.|nom1=Cormen|prénom2=Charles E.|nom2=Leiserson|prénom3=Ronald L.|nom3=Rivest|prénom4=Clifford|nom4=Stein|titre=Introduction to Algorithms|lieu=Cambridge|éditeur=MIT Press and McGraw-Hill|année=2001|numéro d'édition=2|pages totales=1180|isbn=978-0-262-53196-2|lccn=2001031277|numéro chapitre=26|titre chapitre=Chap. 26 Flows|passage=643–700}}. Traduction française : ''Introduction à l'algorithmique'', {{2e|édition}}, [[Éditions Dunod|Dunod]] 2002, « chapitre 26. Flot Maximum ».

{{Palette|Algorithmes sur les graphes}}
{{portail|Informatique théorique | Mathématiques}}

[[Catégorie:Algorithme de la théorie des graphes|Dinic]]
[[Catégorie:Réseau de flot]]