Contenus
ToggleAlgorithme 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 Algorithme De Dinic algorithme de dinic dinitz graphe de niveau](https://complex-systems-ai.com/wp-content/uploads/2016/05/dinic1.png)
Le flot bloquant est le flot maximum pouvant passer dans un chemin donné.
![Algorithme De Dinic Algorithme De Dinic algorithme de dinic dinitz graphe de niveau](https://complex-systems-ai.com/wp-content/uploads/2016/05/dinic2.png)
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 :
![Algorithme De Dinic Algorithme De Dinic algorithme de dinic dinitz graphe de niveau](https://complex-systems-ai.com/wp-content/uploads/2016/05/dinic3.png)
Trouver un chemin augmentant, trouver l’arc limitant :
![Algorithme De Dinic Algorithme De Dinic algorithme de dinic dinitz graphe de niveau](https://complex-systems-ai.com/wp-content/uploads/2016/05/dinic5.png)
Retour à l’étape 3 et 4 :
![Algorithme De Dinic Algorithme De Dinic algorithme de dinic dinitz graphe de niveau](https://complex-systems-ai.com/wp-content/uploads/2016/05/dinic6.png)
Et ainsi de suite jusqu’à ne plus trouver de chemin augmentant :
![Algorithme De Dinic Algorithme De Dinic algorithme de dinic dinitz graphe de niveau](https://complex-systems-ai.com/wp-content/uploads/2016/05/dinic7.png)