Algorithme de Dinic
L’algorithme de Dinic ou Dinitz, s’appuie sur deux notions : un graphe de niveau, et un flot bloquant (level graph & blocking flow).
Pour déterminer le graphe de niveau, nous plaçons la source au niveau 1, ses successeurs au niveau 2 et ainsi de suite.
Le flot bloquant est le flot maximum pouvant passer dans un chemin donné.
L’algorithme de Dinic est le suivant :
- construire un graphe de niveau
- trouver un chemin augmentant (le plus petit) de la source vers le puits
- trouver l’arc limitant le chemin augmentant
- trouver un chemin augmentant de sommet limitant vers le puits
- recommencer les étapes 3 et 4 pour construire un flot bloquant jusqu’à ce qu’il n’y ait plus de chemin augmentant
Exemple
Construction du graphe de niveau :
Trouver un chemin augmentant, trouver l’arc limitant :
Retour à l’étape 3 et 4 :
Et ainsi de suite jusqu’à ne plus trouver de chemin augmentant :
