Algorithme de Dinic

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.

algorithme de dinic dinitz graphe de niveau

Le flot bloquant est le flot maximum pouvant passer dans un chemin donné.

algorithme de dinic dinitz graphe de niveau

L’algorithme de Dinic est le suivant :

  1. construire un graphe de niveau
  2. trouver un chemin augmentant (le plus petit) de la source vers le puits
  3. trouver l’arc limitant le chemin augmentant
  4. trouver un chemin augmentant de sommet limitant vers le puits
  5. 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 :

algorithme de dinic dinitz graphe de niveau

Trouver un chemin augmentant, trouver l’arc limitant :

algorithme de dinic dinitz graphe de niveau

Retour à l’étape 3 et 4 :

algorithme de dinic dinitz graphe de niveau

Et ainsi de suite jusqu’à ne plus trouver de chemin augmentant :

algorithme de dinic dinitz graphe de niveau
Partager