algorithme de Dinic

L'algorithme de Dinic ou algorithme de Dinitz est un algorithme en temps polynomial (et même fortement polynomial) de calcul du flot maximum dans un réseau, publié en 1970 par Yefim Dinitz.Le temps de calcul est en pour un graphe dont est l'ensemble des sommets et l’ensemble des arcs. Il est semblable à l'algorithme d'Edmonds-Karp dont le temps d'exécution est en . Comme lui, il utilise des chemins augmentants de longueur minimale. L'introduction des concepts de graphe de niveau et de flot bloquant permet d'obtenir cette meilleure performance.