L'algorithme de Dinic ou algorithme de Dinitz est un algorithme en temps polynomial (et même fortement polynomial[1]) de calcul du flot maximum dans un réseau, publié en 1970 par Yefim Dinitz[2].
Le temps de calcul est en pour un graphe dont est l'ensemble des sommets et l’ensemble des arcs. Il est semblable à l'algorithme d'Edmonds-Karp dont le temps d'exécution est en . 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 un réseau; et dénotent respectivement la capacité et le flot sur un arc .
La capacité résiduelle est l’application définie comme suit :
si ,
,
,
sinon.
Le graphe résiduel est le graphe , où
.
Un chemin augmentant est un chemin de la source au puits (on dit aussi un --chemin) dans le graphe résiduel. On note la longueur des plus courts chemins de la source au sommet dans ( est la distance de la source à ).
Le graphe de niveau de est le graphe , où
.
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 tel que le graphe avec obtenu en ne conservant que les arcs sur lesquels le flot est strictement inférieur à la capacité ne contient aucun --chemin. Autrement dit, un flot est bloquant si tout --chemin contient un arc où le flot est égal à la capacité.
L'Algorithme
Algorithme de Dinic
Entrée: Un réseau .
Sortie: Un flot de valeur maximale.
Poser pour tout .
Construire le graphe de niveau de à partir de . Si le puits n'est pas accessible, terminer et retourner le flot .
Déterminer un flot bloquant dans .
Augmenter le flot de et retourner au point 2.
Exemple
L'exemple suivant montre l'exécution de l'algorithme de Dinic. Dans le graphe de niveau les valeurs en rouge sont les distances à la source, les arcs en bleu forment un flot bloquant.
1.
Au départ, le flot est nul, donc . 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
avec valeur 4,
avec valeur 6,
avec valeur 4.
2.
Le graphe résiduel 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
avec valeur 5.
La valeur du flot devient 14 + 5 = 19. Le chemin augmentant est composé de 4 arcs.
3.
Le sommet n'est plus accessible dans . 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 étapes, et au plus flots bloquants à calculer, où est le nombre de sommets du réseau.
Le graphe de niveau peut être calculé par un parcours en largeur; un tel parcours prend un temps en , où est le nombre d'arcs. Un flot bloquant peut être calculé en temps . Le temps total de l'algorithme de Dinic est donc en .
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 link/cut tree(en), inventés par Sleator et Tarjan. La détermination du flot bloquant de chaque étape peut être ramenée à , et le temps total à .
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 , et on peut montrer que, de plus, le nombre d'étapes est majoré par et . L'algorithme est donc en temps .
Réseaux de couplages. Dans les réseaux qui interviennent dans la résolution du couplage biparti, le nombre de phases est borné par , ce qui donne un temps borné par . 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[3].
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[4], et par Dinitz lui-même, sur un ton amusé[5]. Dinitz est maintenant membre du département d'informatique de l’université Ben Gourion du Néguev en Israël[6]. 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[7]. 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.
↑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 (Korte et Vygen 2008, p. 6).
↑L'article (Dinitz 2006) contient une longue description des progrès successifs dans les algorithmes de flot maximum.
Bibliographie
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, , 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, (ISBN978-3-540-32880-3, lire en ligne), p. 218–240
Robert E. Tarjan, Data structures and network algorithms,
(en) Bernard H. Korte et Jens Vygen, Combinatorial Optimization : Theory and Algorithms, Springer, coll. « Algorithms and Combinatorics » (no 21), , 627 p. (ISBN978-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 », (ISBN978-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, , 2e éd., 1180 p. (ISBN978-0-262-53196-2, LCCN2001031277), chap. 26 (« Chap. 26 Flows »), p. 643–700. Traduction française : Introduction à l'algorithmique, 2e édition, Dunod 2002, « chapitre 26. Flot Maximum ».