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

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

algorithme de Dinic

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

Trouver un chemin augmentant, trouver l’arc limitant :

algorithme de Dinic

Retour à l’étape 3 et 4 :

algorithme de Dinic

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

algorithme de Dinic
Partager
fr_FRFR
%d blogueurs aiment cette page :