Algorithme de Dinic - Dinic's algorithm

L'algorithme de Dinic ou l'algorithme de Dinitz est un algorithme fortement polynomial pour calculer le débit maximum dans un réseau de débit , conçu en 1970 par l'informaticien israélien (anciennement soviétique) Yefim (Chaim) A. Dinitz. L'algorithme s'exécute dans le temps et est similaire à l' algorithme d'Edmonds-Karp , qui s'exécute dans le temps, en ce sens qu'il utilise les chemins d'augmentation les plus courts. L'introduction des notions de graphe de niveau et de flux bloquant permet à l'algorithme de Dinic d'atteindre ses performances. ${\style d'affichage O(V^{2}E)}$${\style d'affichage O(VE^{2})}$

Histoire

Yefim Dinitz a inventé cet algorithme en réponse à un exercice de pré-classe dans la classe d'algorithmes d' Adelson-Velsky . À l'époque, il n'était pas au courant des faits de base concernant l' algorithme Ford-Fulkerson .

Dinitz mentionne avoir inventé son algorithme en janvier 1969, qui a été publié en 1970 dans la revue Doklady Akademii Nauk SSSR . En 1974, Shimon Even et (son doctorant d'alors) Alon Itai au Technion à Haïfa étaient très curieux et intrigués par l'algorithme de Dinitz ainsi que par l' idée connexe d' Alexander V. Karzanov de bloquer le flux. Cependant il leur était difficile de déchiffrer ces deux articles, chacun étant limité à quatre pages pour répondre aux contraintes de la revue Doklady Akademii Nauk SSSR . Même n'a pas abandonné et, après trois jours d'efforts, a réussi à comprendre les deux documents, à l'exception du problème de maintenance du réseau en couches. Au cours des deux années suivantes, Even donna des conférences sur "l'algorithme de Dinic", prononçant mal le nom de l'auteur tout en le popularisant. Even et Itai ont également contribué à cet algorithme en combinant BFS et DFS , c'est ainsi que l'algorithme est maintenant couramment présenté.

Pendant environ 10 ans après l'invention de l'algorithme de Ford-Fulkerson, on ne savait pas s'il pouvait se terminer en temps polynomial dans le cas général des capacités de bord irrationnelles. Cela a causé l'absence de tout algorithme connu en temps polynomial pour résoudre le problème de flux maximal dans les cas génériques. L'algorithme de Dinitz et l'algorithme d' Edmonds-Karp (publié en 1972) ont tous deux montré indépendamment que dans l'algorithme de Ford-Fulkerson, si chaque chemin d'augmentation est le plus court, la longueur des chemins d'augmentation est non décroissante et l'algorithme se termine toujours.

Définition

Soit un réseau avec et la capacité et le débit du bord , respectivement. ${\style d'affichage G=((V,E),c,f,s,t)}$${\style d'affichage c(u,v)}$${\style d'affichage f(u,v)}$${\style d'affichage (u,v)}$

La capacité résiduelle est une cartographie définie comme, ${\displaystyle c_{f}\colon V\times V\to R^{+}}$

1. si , ${\style d'affichage (u,v)\dans E}$

   ${\style d'affichage c_{f}(u,v)=c(u,v)-f(u,v)}$

2. ${\style d'affichage c_{f}(u,v)=0}$ autrement.

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

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

Un chemin d'augmentation est un chemin – dans le graphe résiduel .${\style d'affichage s}$${\style d'affichage t}$${\style d'affichage G_{f}}$

Définir comme étant la longueur du chemin le plus court de à dans . Alors le graphique de niveau de est le graphique , où ${\displaystyle \operatorname {dist} (v)}$${\style d'affichage s}$${\style d'affichage v}$${\style d'affichage G_{f}}$${\style d'affichage G_{f}}$${\displaystyle G_{L}=((V,E_{L}),c_{f}|_{E_{L}},s,t)}$

${\displaystyle E_{L}=\{(u,v)\in E_{f}\colon \;\operatorname {dist} (v)=\operatorname {dist} (u)+1\}}$.

Un flux bloquant est un flux – tel que le graphe avec ne contient pas de – chemin.${\style d'affichage s}$${\style d'affichage t}$${\style d'affichage f'}$${\displaystyle G'=((V,E_{L}'),s,t)}$${\displaystyle E_{L}'=\{(u,v)\colon \;f'(u,v)<c_{f}|_{E_{L}}(u,v)\}}$${\style d'affichage s}$${\style d'affichage t}$

Algorithme

Algorithme de Dinic

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

Sortie : An – flux de valeur maximale.${\style d'affichage s}$${\style d'affichage t}$${\style d'affichage f}$

1. Définir pour chacun .${\style d'affichage f(e)=0}$${\displaystyle e\in E}$
2. Construire à partir de . Si , arrêt et sortie .${\style d'affichage G_{L}}$${\style d'affichage G_{f}}$${\style d'affichage G}$${\displaystyle \operatorname {dist} (t)=\infty }$${\style d'affichage f}$
3. Trouvez un flux bloquant dans .${\style d'affichage f'}$${\style d'affichage G_{L}}$
4. Ajoutez le flux d'augmentation par et revenez à l'étape 2.${\style d'affichage f}$${\style d'affichage f'}$

Analyse

On peut montrer que le nombre de couches dans chaque flux bloquant augmente d'au moins 1 à chaque fois et qu'il y a donc au plus des flux bloquants dans l'algorithme. Pour chacun d'eux : ${\style d'affichage |V|-1}$

• le graphique de niveau peut être construit par recherche en largeur d'abord dans le temps${\style d'affichage G_{L}}$${\style d'affichage O(E)}$
• un flux bloquant dans le graphique de niveau peut être trouvé dans le temps${\style d'affichage G_{L}}$${\style d'affichage O(VE)}$

avec le temps de fonctionnement total pour chaque couche. En conséquence, le temps d'exécution de l'algorithme de Dinic est . ${\style d'affichage O(E+VE)=O(VE)}$${\style d'affichage O(V^{2}E)}$

En utilisant une structure de données appelée arbres dynamiques , le temps d'exécution de la recherche d'un flux bloquant dans chaque phase peut être réduit à et, par conséquent, le temps d'exécution de l'algorithme de Dinic peut être amélioré à . ${\style d'affichage O(E\log V)}$${\style d'affichage O(VE\log V)}$

Cas spéciaux

Dans les réseaux avec des capacités unitaires, une limite temporelle beaucoup plus forte s'applique. Chaque flux bloquant peut être trouvé dans le temps, et on peut montrer que le nombre de phases ne dépasse pas et . Ainsi, l'algorithme s'exécute dans le temps. ${\style d'affichage O(E)}$${\style d'affichage O({\sqrt {E}})}$${\style d'affichage O(V^{2/3})}$${\style d'affichage O(\min\{V^{2/3},E^{1/2}\}E)}$

Dans les réseaux qui découlent du problème d' appariement bipartite , le nombre de phases est limité par , ce qui conduit donc à la limite temporelle. L'algorithme résultant est également connu sous le nom d' algorithme de Hopcroft-Karp . Plus généralement, cette limite est valable pour tout réseau unitaire - un réseau dans lequel chaque sommet, à l'exception de la source et du puits, a soit un seul front entrant de capacité un, soit un seul front sortant de capacité un, et toutes les autres capacités sont des nombres entiers arbitraires . ${\style d'affichage O({\sqrt {V}})}$${\style d'affichage O({\sqrt {V}}E)}$

Exemple

Ce qui suit est une simulation de l'algorithme de Dinic. Dans le graphique de niveau , les sommets avec des étiquettes en rouge sont les valeurs . Les chemins en bleu forment un flux bloquant. ${\style d'affichage G_{L}}$${\displaystyle \operatorname {dist} (v)}$

	${\style d'affichage G}$	${\style d'affichage G_{f}}$	${\style d'affichage G_{L}}$
1.
	Le flux de blocage consiste en ${\style d'affichage \{s,1,3,t\}}$ avec 4 unités de débit, ${\style d'affichage \{s,1,4,t\}}$ avec 6 unités de débit, et ${\style d'affichage \{s,2,4,t\}}$ avec 4 unités de débit. Par conséquent, le flux de blocage est de 14 unités et la valeur de flux est de 14. Notez que chaque chemin d'augmentation dans le flux de blocage a 3 bords. ${\style d'affichage |f|}$
2.
	Le flux de blocage consiste en ${\style d'affichage \{s,2,4,3,t\}}$ avec 5 unités de débit. Par conséquent, le flux de blocage est de 5 unités et la valeur du flux est de 14 + 5 = 19. Notez que chaque chemin d'augmentation a 4 arêtes. ${\style d'affichage |f|}$
3.
	Puisque ne peut pas être atteint dans , l'algorithme se termine et renvoie un flux avec une valeur maximale de 19. Notez que dans chaque flux bloquant, le nombre d'arêtes dans le chemin d'augmentation augmente d'au moins 1. ${\style d'affichage t}$${\style d'affichage G_{f}}$

Voir également

• Algorithme de Ford-Fulkerson
• Problème de débit maximum

Remarques

Les références

• Yefim Dinitz (2006). " Algorithme de Dinitz : la version originale et la version d'Even " (PDF) . Dans Oded Goldreich ; Arnold L. Rosenberg ; Alan L. Selman (éd.). Informatique théorique : Essais en mémoire de Shimon Even . Springer. p. 218-240. ISBN 978-3-540-32880-3.
• Tarjan, RE (1983). Structures de données et algorithmes de réseau .
• BH Korté ; Jens Vygen (2008). "8.4 Blocage des flux et algorithme de Fujishige". Optimisation combinatoire : théorie et algorithmes (Algorithmes et combinatoire, 21) . Springer Berlin Heidelberg. p. 174-176. ISBN 978-3-540-71844-4.