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.

dinic1

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

dinic2

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 :

dinic3

Trouver un chemin augmentant, trouver l’arc limitant :

dinic5

Retour à l’étape 3 et 4 :

dinic6

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

dinic7

Publicités