Accueil▸Algorithmes et IA▸Algorithme de Bellman-Ford — Plus courts chemins avec poids négatifs

🗺️ Algorithme de Bellman-Ford — Plus courts chemins avec poids négatifs

Observez Bellman-Ford relâcher chaque arête V−1 fois pour trouver les plus courts chemins depuis une source, même avec des poids négatifs, puis effectuer une passe supplémentaire pour détecter les cycles négatifs.

Algorithmes et IA2DAvancé60 FPS

À propos de l'algorithme de Bellman-Ford

L'algorithme de Bellman-Ford, développé indépendamment par Richard Bellman (1958) et Lester Ford Jr. (1956), calcule les plus courts chemins d'un sommet source unique vers tous les autres sommets d'un graphe orienté pondéré. Contrairement à l'algorithme de Dijkstra, il tolère les poids d'arête négatifs, ce qui le rend essentiel pour des applications telles que la détection d'arbitrage sur devises et les protocoles de routage réseau comme RIP. Bellman-Ford est un algorithme de programmation dynamique : il relâche répétitivement chaque arête — remplaçant dist[v] par dist[u] + w(u,v) chaque fois que cette somme est plus petite — pendant exactement V−1 passes, car le plus long chemin le plus court simple possible visite au plus V−1 arêtes. Une dernière passe supplémentaire vérifie si une distance peut encore s'améliorer ; si c'est le cas, le graphe contient un cycle de poids négatif accessible depuis la source, ce qui signifie qu'aucun plus court chemin n'est bien défini. Cela donne à Bellman-Ford une complexité temporelle en O(V·E) et spatiale en O(V), plus lente que le O((V+E) log V) de Dijkstra mais strictement plus générale.

Questions fréquentes

Pourquoi Bellman-Ford a-t-il besoin de V−1 passes ?

Parce que le plus long chemin le plus court possible dans un graphe à V sommets (qui ne répète pas un sommet) peut avoir au plus V−1 arêtes. Chaque passe complète sur toutes les arêtes garantit qu'au moins une arête supplémentaire le long de chaque plus court chemin devient définitive, donc après V−1 passes, toutes les distances les plus courtes se sont entièrement propagées.

Comment Bellman-Ford détecte-t-il les cycles négatifs ?

Après les V−1 passes requises, l'algorithme effectue une passe supplémentaire sur toutes les arêtes. Si une arête peut encore être relâchée — c'est-à-dire qu'une distance diminuerait encore — un cycle de poids négatif accessible depuis la source doit exister, car un arbre de plus courts chemins valide serait déjà stable à ce stade.

Comment Bellman-Ford se compare-t-il à l'algorithme de Dijkstra ?

Les deux calculent les plus courts chemins à source unique, mais Dijkstra utilise une file de priorité gloutonne et exige des poids non négatifs, s'exécutant en O((V+E) log V). Bellman-Ford relâche chaque arête à chaque passe, tolère les poids négatifs, et peut détecter les cycles négatifs, au prix d'un temps d'exécution plus lent en O(V·E).

Bellman-Ford peut-il traiter des graphes non orientés avec des arêtes négatives ?

Non. Toute arête non orientée de poids négatif équivaut à un cycle négatif à deux sommets (u→v et v→u), donc Bellman-Ford le signalerait immédiatement comme un cycle négatif. L'algorithme est conçu pour les graphes orientés ; les poids négatifs n'ont un sens cohérent qu'une fois que les arêtes ont une direction.

⚙ Sous le capot

algorithme de grapheplus court cheminprogrammation dynamiquepoids négatifsrelaxation

2D · HTML5 Canvas 2D · Cible 60 FPS · fonctionne entièrement côté client, sans installation