Algorithme de Busacker & Gowen

Aussi connus sous le nom d’algorithme de Roy, l’algorithme de Busacker & Gowen permet de calculer un flot maximum à coût minimal.

Le principe est simple, la recherche du chemin augmentant se fait par un calcul de plus court chemin (chemin de plus petit coût). Les critères d’optimalité sont équivalant au problème de flot.

L’algorithme se résume ainsi :

  • Construire un graphe de pcc (plus court chemin) à partir du graphe d’écart du flot
    • arc identique au graphe d’écart
    • prix correspondant à l’arc d’origine si dans le même sens, inverse sinon
  • Chercher un pcc de s à t
    • s’il existe, il s’agit du chemin augmentant, le saturé et revenir à l’étape précédente
    • s’il n’existe pas de chemin, fin de l’algorithme.
Publicités