L'algorithme de Bellman–Ford

Certains problèmes de plus court chemin ont des arêtes qui rendent un chemin moins cher : un remboursement, une descente, un taux de change en votre faveur. L'algorithme de Dijkstra ne sait pas les gérer. L'algorithme de Bellman–Ford, si, en remplaçant l'astuce par la patience.

Un graphe aux flèches à sens unique, certaines arêtes négatives, les distances trouvées jusqu'ici sur les nœuds, et un cycle négatif tracé en rouge
Un graphe aux flèches à sens unique, certaines arêtes négatives, les distances trouvées jusqu'ici sur les nœuds, et un cycle négatif tracé en rouge

L'idée

Tout algorithme de plus court chemin repose sur un seul geste, relâcher une arête : si aller jusqu'à u puis suivre l'arête u → v est plus court que le meilleur chemin connu vers v, on l'utilise. L'algorithme de Dijkstra relâche chaque arête une fois, dans un ordre astucieux qui ne marche que si aucune arête n'est négative. Bellman–Ford ne suppose rien de tel. Il relâche chaque arête, dans un ordre fixe quelconque, encore et encore, jusqu'à ce que les distances ne changent plus.

Pas à pas

Donnez au départ la distance 0 et à tous les autres nœuds l'infini. Répétez n − 1 fois, pour n nœuds : parcourez chaque arête u → v et relâchez-la si u a une distance. Arrêtez-vous tôt si un passage entier ne change rien. Puis faites un passage de plus. Si une arête peut encore être relâchée, un cycle de total négatif est accessible depuis le départ ; sinon, chaque distance est la plus courte, et les nœuds retenus donnent les chemins.

Un exemple

Prenez les arêtes à sens unique A → B de longueur 4, A → C 5, B → D 2 et C → B −3, examinées dans cet ordre, depuis A. Le passage 1 donne B 4, C 5 et D 6, puis C → B baisse B à 5 − 3 = 2. Le passage 2 baisse D à 2 + 2 = 4. Le passage 3 ne change rien : la réponse est B 2, C 5, D 4. L'algorithme de Dijkstra aurait rendu B définitif à 4 et D à 6, avant de voir l'arête négative. Ajoutez une arête D → C de longueur −4, et le cycle C → B → D → C totalise −5 : chaque passage fait encore baisser les distances, et le passage de vérification le signale.

Pourquoi n − 1 passages suffisent

Un plus court chemin, quand il existe, ne repasse jamais par un nœud, il a donc au plus n − 1 arêtes. Relâcher chaque arête lors d'un passage allonge d'une arête chaque plus court chemin déjà correct, quel que soit l'ordre des arêtes. Après le passage k, tous les plus courts chemins d'au plus k arêtes sont donc justes, et après n − 1 passages, tous. L'ordre compte quand même pour la vitesse : un bon ordre peut finir en un ou deux passages.

Histoire et usages

Alfonso Shimbel a décrit la méthode en 1955, Lester Ford Jr. en 1956, Edward F. Moore en 1957 et Richard Bellman en 1958 ; elle porte le nom de deux d'entre eux, Bellman et Ford. Ses passages peuvent être faits par chaque routeur de son côté, ce qui en a fait la base des protocoles de routage à vecteur de distance comme RIP. En finance, prendre le logarithme négatif des taux de change transforme une série rentable d'échanges de devises, un arbitrage, en un cycle négatif, que Bellman–Ford peut trouver.

Richard Bellman en 1962, photographié par Alfred Eisenstaedt. Il a publié la méthode des plus courts chemins en 1958, après Shimbel, Ford et Moore.
Richard Bellman en 1962, photographié par Alfred Eisenstaedt. Il a publié la méthode des plus courts chemins en 1958, après Shimbel, Ford et Moore.

À vous d'essayer

Ouvrez l'application et appuyez sur Étape. Chaque arête est à sens unique, et certaines longueurs sont négatives. Chaque étape examine une arête, dans un ordre fixe, et les tuiles montrent le passage et combien de distances il a modifiées. En général, un passage ne change bientôt plus rien et la recherche s'arrête tôt. Cochez Ajouter un cycle négatif et regardez les distances baisser passage après passage, jusqu'à ce que le passage de vérification trouve le cycle et le trace en rouge.

Questions fréquemment posées

Quelle est la complexité en temps de Bellman–Ford ?

O(V · E) pour V nœuds et E arêtes : jusqu'à V − 1 passages, qui examinent chacun toutes les arêtes. Avec l'arrêt anticipé, il est souvent bien plus rapide en pratique, et dans le meilleur cas un seul passage suffit.

Qu'est-ce qu'un cycle négatif ?

Un cycle dont les longueurs d'arêtes totalisent moins que zéro. En faire le tour encore et encore rend un chemin aussi court qu'on veut, donc les plus courtes distances vers tous les nœuds accessibles par lui ne sont pas définies.

Bellman–Ford marche-t-il sur les graphes non orientés ?

Seulement si aucune arête n'est négative : une arête négative non orientée peut être parcourue dans un sens puis dans l'autre, ce qui forme un cycle négatif de deux arêtes. Avec des arêtes positives ou nulles, il marche, mais l'algorithme de Dijkstra est plus rapide.

Qu'est-ce que SPFA ?

Le Shortest Path Faster Algorithm, une version de Bellman–Ford qui, à l'aide d'une file, ne réexamine que les arêtes sortant des nœuds dont la distance vient de changer. Il est souvent bien plus rapide, mais son pire cas est le même.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer Bellman–Ford