07 — Bellman-Ford et A* : poids négatifs et recherche heuristique
Ce que tu vas apprendre
- Bellman-Ford : gérer les poids négatifs par relaxation répétée
- Comment il détecte les cycles de poids négatif
- A* : accélérer Dijkstra avec une heuristique
- Quand choisir chacun des trois algorithmes de plus court chemin
Prérequis
Dijkstra est rapide mais a deux limites : il échoue sur les poids négatifs, et il explore dans toutes les directions sans tenir compte de la destination. Deux algorithmes lèvent ces limites. Bellman-Ford accepte les poids négatifs et détecte les cycles négatifs. A* utilise une connaissance de la destination pour ne pas explorer inutilement. Ces trois algorithmes forment la boîte à outils du plus court chemin.
Bellman-Ford : la relaxation répétée
Là où Dijkstra finalise les sommets un par un dans l'ordre des distances, Bellman-Ford procède différemment : il relâche toutes les arêtes, et répète cette passe V - 1 fois. L'idée : après k passes, on connaît le plus court chemin utilisant au plus k arêtes. Comme un plus court chemin sans cycle utilise au plus V - 1 arêtes, V - 1 passes suffisent.
pythondef bellman_ford(sommets, aretes, source):
# aretes = liste de (u, v, poids)
distances = {s: float("inf") for s in sommets}
distances[source] = 0
for _ in range(len(sommets) - 1): # V - 1 passes
for u, v, poids in aretes:
if distances[u] + poids < distances[v]:
distances[v] = distances[u] + poids # relaxation
return distances
La complexité est O(V × E) : pour chacune des V - 1 passes, on parcourt les E arêtes. C'est plus lent que Dijkstra, mais Bellman-Ford fonctionne avec des poids négatifs, parce qu'il ne fait aucune hypothèse gloutonne de finalisation. Il continue de relâcher toutes les arêtes, ce qui lui permet de découvrir tardivement qu'un chemin passant par une arête négative est meilleur.
Détecter les cycles de poids négatif
Bellman-Ford offre un bonus que Dijkstra ne peut pas donner : détecter les cycles de poids négatif. Un tel cycle est un piège pour le « plus court chemin » : on pourrait le parcourir indéfiniment en diminuant le coût à chaque tour, donc le plus court chemin n'existe pas (il tend vers moins l'infini).
La détection est simple : après les V - 1 passes, on fait une passe de plus. Si une distance peut encore être améliorée, c'est qu'un cycle de poids négatif existe.
python # après les V-1 passes : une passe de vérification
for u, v, poids in aretes:
if distances[u] + poids < distances[v]:
raise ValueError("Cycle de poids négatif détecté")
Cette capacité a des usages concrets : détecter une opportunité d'arbitrage en finance (une suite de conversions de devises qui rapporte de l'argent forme un cycle négatif), ou vérifier la cohérence de contraintes.
A* : Dijkstra guidé
A* (« A étoile ») répond à l'autre limite de Dijkstra. Dijkstra explore dans toutes les directions, y compris à l'opposé de la destination. Si on cherche un chemin de Paris à Marseille, Dijkstra explore aussi vers Lille avant d'avoir fini. A* corrige ça avec une heuristique : une estimation de la distance restante jusqu'à la destination.
A* choisit le prochain sommet à explorer non pas selon sa seule distance depuis la source (comme Dijkstra), mais selon la somme : distance déjà parcourue + estimation de ce qui reste. Il privilégie ainsi les sommets qui semblent aller dans la bonne direction.
Dijkstra choisit le sommet minimisant : g(n)
A* choisit le sommet minimisant : g(n) + h(n)
g(n) = coût réel depuis la source
h(n) = estimation heuristique du coût restant jusqu'au butL'heuristique typique, pour un déplacement sur une carte, est la distance à vol d'oiseau vers la destination : facile à calculer, et toujours inférieure ou égale à la distance réelle. C'est la condition pour que A* reste correct : l'heuristique doit être admissible, c'est-à-dire ne jamais surestimer le coût restant. Sous cette condition, A* trouve le vrai plus court chemin, mais en explorant beaucoup moins de sommets que Dijkstra.
Si l'heuristique vaut zéro partout (aucune information sur la destination), A* se comporte exactement comme Dijkstra. A* est donc une généralisation de Dijkstra qui exploite une connaissance du but.
Choisir le bon algorithme
| Algorithme | Poids | Détecte cycle négatif | Vitesse | Cas d'usage |
|---|---|---|---|---|
| BFS | non pondéré | — | O(V + E) | moins d'arêtes |
| Dijkstra | positifs | non | O((V+E) log V) | plus court pondéré, source unique |
| Bellman-Ford | quelconques | oui | O(V × E) | poids négatifs, arbitrage |
| A* | positifs | non | ≤ Dijkstra | but connu + heuristique |
La règle de décision :
- arêtes sans poids → BFS ;
- poids positifs, pas d'info sur la destination → Dijkstra ;
- poids potentiellement négatifs, ou besoin de détecter un cycle négatif → Bellman-Ford ;
- poids positifs et destination précise avec une bonne heuristique (jeux, GPS, robotique) → A*.
A* est central dans les jeux vidéo (déplacement d'unités sur une carte) et la navigation, parce qu'une bonne heuristique réduit énormément l'espace exploré. Le dernier article de la série rassemble ces algorithmes autour de cas réels et montre comment reconnaître un problème de graphe dans du code de tous les jours.
Sources
- Bellman, R. (1958). On a Routing Problem. Quarterly of Applied Mathematics, 16(1).
- Ford, L. R. (1956). Network Flow Theory. RAND Corporation.
- Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2). (Algorithme A*)
- Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 24.1 "The Bellman-Ford Algorithm". MIT Press.