Algorithme Push-Relabel
- Introduite par
- Andrew V. Goldberg and Robert E. Tarjan
- Année
- 1988
- Type
- algorithm
- Famille
- Graph Algorithms
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
L'algorithme Push-Relabel, développé par Andrew V. Goldberg et Robert E. Tarjan en 1988, est une méthode très efficace pour calculer le flot maximum dans les réseaux.
Contrairement aux méthodes par chemins augmentants, il maintient un préflot et utilise des opérations locales de poussée (push) et de re-étiquetage global (relabel) pour diriger le flot vers la cible, atteignant ainsi une complexité dans le pire des cas supérieure.
L’intuition derrière la méthode
L'algorithme maintient une 'hauteur' ou 'étiquette de distance' pour chaque nœud et utilise un préflot (où les nœuds peuvent temporairement dépasser la demande de la cible). Il pousse de manière répétée l'excès de flot des nœuds à étiquette plus élevée vers leurs voisins à étiquette plus basse et re-étiquette les nœuds pour créer des chemins vers la cible. L'idée clé est qu'en maintenant des invariants de hauteur et en utilisant des structures de données efficaces, l'algorithme évite d'explorer l'ensemble du graphe de manière répétée, comme le font les méthodes par chemins augmentants. L'algorithme se termine lorsque tout le préflot a atteint la cible.
Histoire
Goldberg et Tarjan ont publié leur algorithme push-relabel en 1988, introduisant un paradigme fondamentalement différent pour le calcul du flot maximum. Leur algorithme a atteint une complexité dans le pire des cas de O(V³), une amélioration par rapport à O(VE²) d'Edmonds-Karp. Au cours des décennies suivantes, de nombreuses variantes ont été développées, y compris les heuristiques de trou (Goldberg et Tarjan, 1990), les règles de plus haute hauteur (highest-label rules), et les dernières variantes atteignant des performances empiriques quasi linéaires sur des réseaux réels.
Quand l’utiliser
Appliquer l'algorithme push-relabel pour calculer le flot maximum dans les réseaux larges et denses où les méthodes par chemins augmentants deviennent inefficaces. Il est particulièrement efficace pour les réseaux comportant des milliers ou des millions d'arêtes. L'utiliser lorsque vous avez besoin d'une performance garantie en temps polynomial et que vous souhaitez tirer parti des structures de données modernes. Pour les réseaux épars ou à des fins éducatives, les méthodes par chemins augmentants peuvent être plus simples à comprendre et à implémenter.
Limites et points d’attention
- Plus complexe à comprendre et à implémenter que les méthodes par chemins augmentants
- Nécessite une gestion attentive des structures de données (listes de décharge, heuristiques de trou) pour des performances optimales
- La complexité dans le pire des cas est toujours plus élevée que celle de certains algorithmes spécialisés pour des classes de graphes particulières
- Compréhension moins intuitive du processus de solution par rapport aux chemins augmentants
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Complexité temporelle dans le pire des cas supérieure : O(V³) ou O(V²√E) avec l'heuristique de trou (gap heuristic)
- Très efficace en pratique, en particulier pour les réseaux larges et denses
- Localité des opérations (push/relabel) permettant de bonnes performances de cache
- Adapté à la parallélisation et aux implémentations distribuées
- Multiples variantes d'implémentation pour différentes structures de problèmes
Applications
- Routage de réseau : calcul du débit maximum dans les réseaux de communication à grande échelle
- Traitement d'images : utilisation du flot maximum pour la segmentation d'images et les applications de matting
- Optimisation aérienne : détermination du flot passagers maximum à travers des réseaux de routage complexes
- Analyse de réseaux électriques : calcul de la capacité de transmission de puissance maximale dans les réseaux électriques
- Gestion de la chaîne d'approvisionnement : optimisation du flux de produits à travers des réseaux de distribution à plusieurs niveaux
- Réseaux biologiques : analyse du flot maximum dans les réseaux métaboliques et d'interaction protéique
Comment ça marche
Comment ça marche
Définir la hauteur de la source au nombre de sommets, toutes les autres hauteurs à zéro. Saturer toutes les arêtes sortant de la source, créant un préflot initial (excès aux nœuds voisins).
Sélectionner de manière répétée un nœud actif (avec excès de flot) et soit pousser l'excès vers un voisin de hauteur inférieure, soit re-étiqueter le nœud pour augmenter sa hauteur. Utiliser des stratégies de sélection et des opérations de décharge efficaces pour minimiser les itérations.
Continuer jusqu'à ce qu'il ne reste plus de nœuds actifs, auquel cas tout le préflot a été résolu en un flot maximum de la source à la cible.
Pièges courants
- Mise à jour incorrecte des hauteurs ou des opérations de poussée entraînant des flots non maximaux
- Négliger l'utilisation des heuristiques de trou et de la sélection efficace des nœuds, résultant en de mauvaises performances pratiques
- Ne pas maintenir correctement l'invariant de préflot (excès aux nœuds et contraintes de capacité sur les arêtes)
Questions fréquentes
Quelle est la différence entre préflot et flot ?
Le préflot permet temporairement aux nœuds de détenir un excès de flot (le flot entrant moins le flot sortant peut être positif), tandis que le flot réel doit être conservé à tous les nœuds sauf la source et la cible. L'algorithme se termine lorsque le préflot devient un flot valide.
Quel est le but de la fonction de hauteur ?
Les hauteurs créent une mesure quasi-distance : le flot ne peut être poussé qu'en descente (des hauteurs plus élevées vers les plus basses), empêchant les cycles inutiles et assurant la terminaison. Les hauteurs sont augmentées par re-étiquetage pour créer de nouveaux chemins si nécessaire.
Qu'est-ce que l'heuristique de trou (gap heuristic) et pourquoi est-elle importante ?
L'heuristique de trou détecte lorsqu'aucun nœud n'a de hauteur dans une certaine plage, indiquant que certains nœuds ne peuvent pas atteindre la cible. Ces nœuds et leur excès sont rapidement identifiés et traités, améliorant considérablement les performances pratiques.
Comment le push-relabel se compare-t-il en pratique à Edmonds-Karp ?
Le push-relabel a une meilleure complexité dans le pire des cas et surpasse généralement Edmonds-Karp sur les grands réseaux, mais pour les petits réseaux ou les graphes épars, Edmonds-Karp peut être plus simple à implémenter avec des performances compétitives.
Méthodes associées
Sources
Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.
Ouvrir la référence DOICopié.Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.
Ouvrir la référence de la publicationCopié.