Flot maximum

Maintenant nous cherchons à installer des barrages sur un nombre minimum de rues pour empêcher toute circulation de la source à la destination. On considère les mêmes deux sommets de l’exercice précédent. Combien de barrages sont nécessaires au minimum ?

Modélisation comme un problème de flot

Dans le problème dual on cherche un nombre maximum de chemins arc-disjoints de la source à la destination. Une petite modification de votre programme linéaire pour les plus courts chemins peut répondre à la question. Modélisez le problème comme un problème de flot maximum dans un graphe orienté où la capacité de tout arc est 1.

Notes

Le théorème de Menger’1927 dit que le nombre minimum de router à couper pour déconnecter la source de la destination est égal au nombre maximum de chemins arc-disjoints entre la source et la destination.

Si la programmation linéaire peut efficacement résoudre les problèmes de flot maximum, il existe des algorithmes combinatoires dédiés plus efficaces, comme par exemple l’algorithme de Dinic implémenté ici.