Algorithme de Bellman-Ford
- Introduite par
- Richard Bellman and Lester R. Ford
- Année
- 1956
- 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 de Bellman-Ford, développé par Richard Bellman et Lester R. Ford dans les années 1950, est un algorithme fondamental pour calculer les plus courts chemins dans des graphes pondérés pouvant contenir des poids d'arêtes négatifs.
Contrairement à l'algorithme de Dijkstra, il gère correctement les poids négatifs et peut détecter la présence de cycles de poids négatif.
L’intuition derrière la méthode
L'algorithme fonctionne en relaxant itérativement les arêtes : pour chaque arête, il vérifie si passer par cette arête offre un chemin plus court vers la destination que le meilleur chemin connu actuellement. En répétant ce processus pour toutes les arêtes V-1 fois, où V est le nombre de sommets, l'algorithme garantit de trouver le plus court chemin même avec des poids négatifs. L'idée clé est que tout plus court chemin dans un graphe à V sommets contient au plus V-1 arêtes ; si les distances s'améliorent encore après V-1 itérations, un cycle négatif doit exister.
Histoire
Richard Bellman a développé l'algorithme en 1958 en utilisant les principes de la programmation dynamique, tandis que Lester R. Ford a découvert indépendamment une approche similaire pour les flux réseau en 1956. L'algorithme a été développé et amélioré davantage dans les années 1960, avec des applications s'étendant au routage réseau et aux applications économiques. Les variantes modernes incluent l'algorithme Shortest Path Faster Algorithm (SPFA) et diverses optimisations pour des structures de graphes spécifiques, bien que l'approche de base de Bellman-Ford reste une référence classique dans la conception d'algorithmes.
Quand l’utiliser
Appliquer l'algorithme de Bellman-Ford lors du calcul des plus courts chemins dans des graphes avec des poids d'arêtes négatifs. Il est essentiel pour la détection d'arbitrage monétaire, les protocoles réseau où les poids peuvent être négatifs, et toute application où les coûts ou poids négatifs sont significatifs. Utiliser l'algorithme de Dijkstra si tous les poids sont non négatifs, car il est plus efficace. Pour détecter les cycles négatifs sans calculer les chemins, cet algorithme est également approprié.
Limites et points d’attention
- Plus lent que Dijkstra pour les poids non négatifs : O(VE) contre O((V+E)logV)
- Moins efficace pour les graphes épars par rapport à d'autres algorithmes
- Nécessite que toutes les arêtes soient explicitement listées, ce qui le rend moins adapté aux graphes implicites ou dynamiques
- Aucune guidance heuristique disponible pour accélérer le calcul
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Gère correctement les graphes avec des poids d'arêtes négatifs
- Détecte les cycles de poids négatif, empêchant des résultats erronés pour les plus courts chemins
- Plus simple à comprendre et à implémenter que certains algorithmes avancés de plus court chemin
- Garanti de trouver les plus courts chemins en temps O(VE)
- Fonctionne sur les graphes dirigés et non dirigés (avec prudence sur les non dirigés)
Applications
- Détection d'arbitrage monétaire : identification de cycles profitables dans les graphes de taux de change
- Protocoles de routage réseau : calcul des plus courts chemins où les coûts de liaison peuvent varier ou être négatifs
- Théorie des jeux : résolution de problèmes de plus court chemin avec des arêtes de pénalité ou des facteurs d'escompte
- Robotique : planification de trajectoire dans des environnements avec des forces répulsives (poids négatifs)
- Dispatch économique : optimisation de la production d'électricité avec des fonctions de coût incluant des termes négatifs
- Télécommunications : recherche d'itinéraires optimaux lorsque les poids des liaisons représentent des métriques de délai ou de qualité
Comment ça marche
Comment ça marche
Définir la distance de la source à zéro et toutes les autres distances à l'infini ; éventuellement, définir tous les prédécesseurs à nul.
Répéter V-1 fois : pour chaque arête (u, v) de poids w, si distance[u] + w est inférieur à distance[v], mettre à jour distance[v] et le prédécesseur de v.
Vérifier toutes les arêtes une fois de plus ; si une distance s'améliore, un cycle de poids négatif existe. Retourner une erreur ou identifier le cycle de manière appropriée.
Pièges courants
- Oublier d'effectuer l'itération supplémentaire pour détecter les cycles négatifs
- Supposer que l'algorithme fonctionne correctement sur les graphes non dirigés avec des arêtes négatives (peut créer des cycles négatifs virtuels)
- Utiliser l'algorithme alors que Dijkstra est suffisant, entraînant une perte de performance inutile
Questions fréquentes
Pourquoi l'algorithme nécessite-t-il exactement V-1 itérations ?
Tout chemin dans un graphe à V sommets comporte au plus V-1 arêtes. En itérant V-1 fois, l'algorithme permet à l'information de distance de se propager à travers tout le graphe. Une V-ième itération n'améliorera les distances que si un cycle négatif existe.
Comment l'algorithme peut-il détecter les cycles négatifs ?
Après avoir terminé V-1 itérations, effectuez une passe de relaxation supplémentaire. Si une distance diminue, un cycle négatif existe. Les nœuds impliqués dans le cycle peuvent être identifiés par rétro-propagation à l'aide des pointeurs prédécesseurs.
Quelle est la complexité temporelle et comment se compare-t-elle à Dijkstra ?
Bellman-Ford s'exécute en temps O(VE), où V est le nombre de sommets et E le nombre d'arêtes. Dijkstra s'exécute en O((V+E)logV) avec un tas binaire. Bellman-Ford est plus lent mais gère les poids négatifs ; Dijkstra est plus rapide mais nécessite des poids non négatifs.
Bellman-Ford peut-il fonctionner sur des graphes non dirigés avec des poids négatifs ?
Techniquement oui, mais cela peut créer des cycles négatifs artificiels en raison de la nature bidirectionnelle des arêtes. Une attention particulière est nécessaire pour interpréter correctement les résultats. Pour les graphes non dirigés, envisagez des approches alternatives.
Méthodes associées
Sources
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.
Ouvrir la référence DOICopié.Ford, L. R. (1956). Network Flow Theory. RAND Corporation Paper P-923.
Ouvrir la référence de la publicationCopié.