Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de poussage/réétiquetage
Résumé
Lalgorithme push-relabel (traduit en français par algorithme de poussage/réétiquetage), aussi appelé algorithme de Goldberg-Tarjan, est l'un des algorithmes les plus efficaces pour calculer un flot maximum dans un réseau. Il a été publié par Goldberg et Tarjan en 1986. L'algorithme général a une complexité en temps en (ici est l'ensemble des sommets, et l'ensemble des arcs du graphe) ; une implémentation plus sophistiquée, utilisant une règle de sélection de sommets par pile a un temps d'exécution en ; une autre règle, celle qui sélectionne le sommet actif le plus élevé (dans un sens précisé plus loin) permet d'obtenir la complexité . Enfin l'implémentation avec une structure de données introduite par Daniel Sleator et Robert E. Tarjan et appelée arbre dynamique, et notamment avec un donne un temps d'exécution majoré par . Tous ces temps sont meilleurs que la majoration en qui est celle de l'algorithme d'Edmonds-Karp.
thumb|upright=1.5|Sur chaque arc, la valeur du flot et la capacité. La capacité de l'arc opposé est nulle (sauf s'il existe déjà), la valeur du flot son opposée.
thumb|upright=1.5|Réseau résiduel. La capacité résiduelle est la différence entre la capacité et le flot.
Dans un réseau, le flot entrant dans un sommet doit être égal à celui qui en sort (à l'exception des deux sommets qui sont la source et le puits). C'est le principe de conservation de flot, aussi appelé loi de Kirchhoff. On ne peut donc pas « accumuler » des valeurs à l'intérieur du réseau. Un préflot est une notion dans laquelle cette condition de conservation est affaiblie, en autorisant les sommets à avoir une valeur de flot entrant plus importante que celle du flot sortant. La différence est appelée l'excédent du sommet. Un sommet à excédent positif est dit actif. L'excédent de flot peut être diminué par transfert sur les arcs du graphe résiduel. Le flot est « poussé » (pushed) à travers le réseau en respectant une valeur appelée hauteur des sommets. Les hauteurs sont une approximation de la distance au puits; le flot n'est poussé que vers des distances au puits plus courtes.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.