Calculateur Bellman-Ford

Pseudocode

Bellman-Ford est l'algorithme de plus court chemin qui échange l'astuce contre la généralité. Ni file de priorité ni décision d'ordre, seulement le relâchement répété de toutes les arêtes.

BellmanFord(graphe, source):
    pour chaque sommet v: dist[v] = infini
    dist[source] = 0

    répéter V - 1 fois:
        modifie = faux
        pour chaque arête (u, v, w):
            si dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                modifie = vrai
        si non modifie: sortir       // sortie anticipée

    // Une passe supplémentaire détecte les cycles négatifs
    pour chaque arête (u, v, w):
        si dist[u] + w < dist[v]:
            signaler un cycle négatif atteignable

L'invariant est qu'après la passe i, tout plus court chemin utilisant au plus i arêtes est correct. Comme un plus court chemin dans un graphe sans cycle négatif emprunte au plus V - 1 arêtes, V - 1 passes règlent tout. Si une V-ième passe améliore encore quelque chose, c'est qu'un chemin raccourcit sans limite, ce qui est exactement la définition d'un cycle négatif.

Exemple détaillé, étape par étape

Exécute Bellman-Ford depuis A sur un graphe comportant une arête négative que Dijkstra traiterait mal. Les arêtes sont relâchées dans l'ordre fixe indiqué.

Graphe d'exemple: Arêtes orientées A vers B (4), A vers C (5), B vers C (-3) et C vers D (2).

1. Initialiser. dist = A 0, B infini, C infini, D infini.
2. Passe 1. A vers B fixe dist[B] = 4. A vers C fixe dist[C] = 5. B vers C propose 4 + (-3) = 1, mieux que 5, donc dist[C] = 1. C vers D fixe dist[D] = 1 + 2 = 3. Après une passe: A 0, B 4, C 1, D 3.
3. Passe 2. Toutes les arêtes sont réexaminées et rien ne s'améliore. Avec le test de sortie anticipée, l'algorithme s'arrête ici au lieu d'exécuter les passes restantes.
4. Test du cycle négatif. Un balayage de plus sur les quatre arêtes ne trouve aucune amélioration, il n'existe donc aucun cycle négatif atteignable depuis A et les distances sont définitives.
5. Pourquoi Dijkstra échoue ici. Dijkstra fixerait C à la distance 5 dès que C quitterait la file de priorité, car il suppose qu'un sommet fixé ne peut plus être amélioré. L'arête ultérieure B vers C de poids -3 serait alors ignorée, et Dijkstra annoncerait dist[C] = 5 et dist[D] = 7 au lieu des valeurs correctes 1 et 3.

Les distances correctes sont A 0, B 4, C 1, D 3. Une seule arête négative suffit à mettre Dijkstra en défaut, et c'est la raison d'être de Bellman-Ford.

Complexité et son origine

Temps: O(VE) · Espace: O(V)

L'algorithme effectue V - 1 passes, chacune relâchant les E arêtes une fois, d'où O(VE). L'espace se limite à une distance et un parent par sommet, soit O(V), remarquablement indépendant de E. Sur un graphe dense où E approche V au carré, le temps tend vers O(V au cube), raison pour laquelle Bellman-Ford est réservé aux cas comportant réellement des poids négatifs. Le test de sortie anticipée, qui interrompt dès qu'une passe ne change rien, termine souvent en quelques passes sur des graphes réels même si le pire cas reste V - 1.

Quand utiliser Algorithme de Bellman-Ford, et quand l'éviter

Bellman-Ford est strictement plus général que Dijkstra et strictement plus lent. Ne le choisis que si tu as vraiment besoin de ce qu'il apporte.

Pièges fréquents

• N exécuter que V - 1 passes et s arrêter là. Sans la V-ième passe supplémentaire, impossible de distinguer des distances correctes de distances qui continuent de chuter à travers un cycle négatif. La passe de détection n'est pas une formalité comptable, c'est ce qui rend le résultat digne de confiance.
• Croire qu un cycle négatif détecté affecte tout le graphe. La passe supplémentaire ne détecte que les cycles atteignables depuis la source. Un cycle négatif situé dans une composante inatteignable reste invisible et, pour une question à source unique, sans importance. S'il te faut tous les cycles négatifs, pars d'une source virtuelle reliée à chaque sommet.
• Relâcher depuis des sommets à distance infinie. Dans les langages où l'infini est un grand entier plutôt qu'un flottant, dist[u] + w déborde et devient négatif, créant des améliorations fantômes. Protège le relâchement en vérifiant que dist[u] n'est pas encore infini.
• L utiliser par prudence sur des graphes positifs. Sur un graphe sans arête négative, Bellman-Ford calcule exactement ce que calcule Dijkstra mais peut être des ordres de grandeur plus lent. La généralité n'est pas gratuite.
• Attendre des plus courts chemins malgré un cycle négatif. Quand un cycle négatif est atteignable, il n'existe aucun plus court chemin, et non pas un chemin simplement inconnu: on peut toujours refaire un tour du cycle et descendre plus bas. Signale le cycle plutôt que de renvoyer une distance.

Questions fréquentes

À quoi sert l'algorithme de Bellman-Ford?

Il calcule les plus courts chemins depuis une source unique dans des graphes pouvant comporter des poids négatifs, et détecte les cycles négatifs. En pratique il sous-tend les protocoles de routage à vecteur de distance comme RIP, la détection d'arbitrage de devises où les taux de change deviennent des logarithmes négatifs, et les problèmes de planification où certaines transitions rapportent au lieu de coûter.

Pourquoi utiliser Bellman-Ford plutôt que Dijkstra?

Parce que Dijkstra est faux avec des arêtes négatives. Dijkstra fixe un sommet définitivement dès qu'il quitte la file de priorité, en supposant que rien ne pourra l'améliorer ensuite, et une arête négative découverte plus tard brise cette hypothèse. Bellman-Ford ne prend aucun tel engagement et reste donc correct, au prix de O(VE) au lieu de O((V + E) log V).

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

Après V - 1 passes de relâchement, tout plus court chemin possible est déjà définitif, car un chemin simple compte au plus V - 1 arêtes. Si une passe de plus sur toutes les arêtes améliore encore une distance, cette amélioration ne peut provenir que d'un cycle de poids total négatif atteignable depuis la source.

Quelle est la complexité temporelle de Bellman-Ford?

O(VE) en temps et O(V) en espace. Il effectue V - 1 passes sur les E arêtes. Avec l'optimisation de sortie anticipée il s'arrête souvent bien plus tôt sur des graphes réels, mais le pire cas est inchangé. Sur les graphes denses cela approche O(V au cube).

Bellman-Ford gère-t-il les poids négatifs?

Oui, c'est toute sa raison d'être, à condition qu'aucun cycle négatif ne soit atteignable depuis la source. Avec des poids négatifs mais sans cycle négatif, il renvoie des plus courts chemins corrects. Avec un cycle négatif atteignable, aucun plus court chemin n'existe, et l'algorithme le signale plutôt que de renvoyer une distance dénuée de sens.