L'algorithme de Bellman-Ford expliqué

Mohammed Islam Hadjoudj

Ingénieur expert en recherche opérationnelle

1. Introduction à l'algorithme de Bellman-Ford

L'algorithme de Bellman-Ford est l'un des algorithmes les plus fondamentaux de la théorie des graphes. Nommé d'après ses pionniers, Richard Bellman et Lester Ford Jr., qui l'ont publié à la fin des années 1950, cet algorithme résout le problème du plus court chemin à source unique. Autrement dit, il trouve le plus court chemin depuis un nœud de départ vers tous les autres nœuds d'un graphe pondéré.

Si vous connaissez l'algorithme de Dijkstra, vous vous demandez peut-être : « Pourquoi avons-nous besoin d'un autre algorithme pour exactement le même problème ? » La réponse tient à la polyvalence. Si l'algorithme de Dijkstra est plus rapide et très efficace pour les graphes où tous les poids d'arêtes sont positifs (comme les réseaux routiers physiques), il s'effondre complètement dès qu'on introduit des poids d'arêtes négatifs. Bellman-Ford, en revanche, accepte les poids négatifs et fournit un mécanisme robuste pour les gérer, garantissant des calculs de plus court chemin exacts même dans des scénarios économiques ou réseau complexes.

De plus, Bellman-Ford possède un super-pouvoir unique : il peut détecter les cycles négatifs. Un cycle négatif est une boucle dans un graphe où la somme des poids des arêtes est inférieure à zéro. Si un tel cycle existe, la notion de « plus court chemin » perd tout son sens, car on pourrait théoriquement parcourir le cycle indéfiniment pour atteindre une longueur de chemin de moins l'infini. Bellman-Ford détecte cette anomalie et vous en avertit, ce qui en fait un outil indispensable pour la détection d'anomalies dans divers domaines, y compris l'arbitrage financier.

2. Le problème de Dijkstra : les poids négatifs

Pour vraiment saisir la nécessité de l'algorithme de Bellman-Ford, il faut d'abord examiner la limite critique de l'algorithme de Dijkstra.

L'algorithme de Dijkstra repose sur un principe glouton. Il maintient un ensemble de nœuds non visités et, à chaque étape, sélectionne le nœud dont la distance connue à la source est la plus petite. Une fois un nœud sélectionné, Dijkstra considère sa plus courte distance comme « définitive » et ne la revisite jamais pour la mettre à jour. Cette hypothèse fonctionne parfaitement lorsque tous les poids d'arêtes sont positifs, car ajouter une arête à un chemin en augmente toujours la longueur totale. Ainsi, aucun chemin découvert plus tard ne saurait être plus court que celui déjà finalisé.

Mais que se passe-t-il lorsque nous introduisons un poids d'arête négatif ?

Considérons un graphe simple à trois nœuds : A, B et C. Le nœud de départ est A.

• L'arête de A vers B a un poids de 5.
• L'arête de A vers C a un poids de 10.
• L'arête de B vers C a un poids de -8.

Si nous exécutons l'algorithme de Dijkstra depuis A, il explore d'abord les voisins B (distance 5) et C (distance 10). Le nœud finalisé ensuite est B, car 5 est inférieur à 10. La plus courte distance vers B est désormais fixée à 5. Il examine ensuite les arêtes issues de B. Il voit l'arête de B vers C de poids -8. Le nouveau chemin vers C est A -> B -> C, d'un poids total de 5 + (-8) = -3. Mais l'algorithme de Dijkstra est glouton ; s'il avait finalisé C avant de repérer l'arête négative, ou si le graphe était plus complexe, Dijkstra ne mettrait pas correctement C à jour et renverrait un résultat erroné. Dans des graphes plus complexes, l'hypothèse gloutonne de Dijkstra selon laquelle « les chemins plus longs ne peuvent pas devenir plus courts » s'effondre.

C'est là que Bellman-Ford excelle. Il abandonne l'approche gloutonne et relâche plutôt systématiquement toutes les arêtes à plusieurs reprises, garantissant que, même si une arête négative offre un raccourci plus court plus tard dans le processus, l'algorithme identifiera et mettra à jour correctement le plus court chemin.

3. Le danger des cycles négatifs

Un cycle négatif est une boucle fermée dans un graphe où la somme des poids des arêtes qui composent le cycle est inférieure à zéro. Ce concept est fondamental pour comprendre pourquoi Bellman-Ford est conçu ainsi.

Imaginez un graphe dont les nœuds A, B et C forment un triangle. Les poids des arêtes sont A vers B (2), B vers C (-5) et C vers A (1). Le poids total de ce cycle est 2 + (-5) + 1 = -2. Si vous voulez trouver le plus court chemin de A vers n'importe quel autre nœud, vous pourriez simplement parcourir ce cycle indéfiniment. À chaque tour de boucle, votre distance totale diminue de 2. Après un tour, la distance est de -2 ; après dix tours, de -20. En tendant vers l'infini, le plus court chemin tend vers moins l'infini.

En présence d'un cycle négatif accessible depuis le nœud source, le problème du plus court chemin n'a pas de solution. Les algorithmes classiques se retrouveraient piégés dans une boucle infinie, cherchant sans cesse un chemin « plus court ». Bellman-Ford évite élégamment cette boucle infinie et détecte explicitement la présence du cycle.

4. Concept clé : la relaxation d'arête

Le fondement de l'algorithme de Bellman-Ford est un processus appelé relaxation d'arête. C'est le mécanisme par lequel l'algorithme met à jour la plus courte distance connue vers un nœud.

Définissons deux tableaux (ou dictionnaires) :

• distance[] : stocke la plus courte distance connue depuis le nœud de départ vers tous les autres. Au départ, la distance au nœud de départ est 0 et celle de tous les autres nœuds est fixée à l'infini (∞).
• predecessor[] (facultatif mais utile) : stocke le nœud qui précède immédiatement un nœud donné sur le plus court chemin. Il sert à reconstruire le chemin réel une fois l'algorithme terminé.

L'opération de relaxation pour une arête du nœud u vers le nœud v de poids w est définie comme suit :

if distance[u] + w < distance[v]:
    distance[v] = distance[u] + w
    predecessor[v] = u

En clair : « Si la distance connue au nœud u plus le poids de l'arête de u vers v est inférieure à la plus courte distance connue jusqu'ici vers le nœud v, alors nous avons trouvé un meilleur chemin ! Mettez à jour la plus courte distance vers v. »

L'algorithme de Bellman-Ford parcourt simplement toutes les arêtes du graphe et tente de les relâcher encore et encore.

5. Exécution pas à pas de Bellman-Ford

Parcourons maintenant les étapes précises de l'algorithme.

Soit V le nombre de sommets (nœuds) du graphe et E le nombre d'arêtes. L'algorithme se déroule en trois phases principales.

Phase 1 : Initialisation

Initialisez le tableau distance. Fixez la distance au nœud de départ à 0 et celle de tous les autres nœuds à l'infini. Cela traduit qu'au départ, nous ne savons pas comment atteindre un autre nœud que le point de départ.

Phase 2 : Relaxation répétée

C'est le cœur de l'algorithme. Nous devons relâcher toutes les arêtes du graphe, et ce V - 1 fois.

Pourquoi exactement V - 1 fois ? Considérons un graphe à V nœuds. Le plus long chemin simple le plus court possible (un chemin sans cycle) entre deux nœuds quelconques compte au plus V - 1 arêtes. Dans le pire des cas, il faut une itération complète sur toutes les arêtes pour garantir l'exactitude des chemins d'une arête. Il en faut deux pour garantir ceux de deux arêtes, et ainsi de suite. Ainsi, après V - 1 itérations, s'il n'y a pas de cycles négatifs, nous sommes assurés d'avoir trouvé le plus court chemin absolu vers chaque nœud, quel que soit l'ordre de traitement des arêtes.

1. Démarrez une boucle qui s'exécute V - 1 fois.
2. À l'intérieur de cette boucle, parcourez chaque arête du graphe.
3. Pour chaque arête (u, v) de poids w, tentez de la relâcher : si distance[u] + w < distance[v], mettez à jour distance[v].

Phase 3 : Détection des cycles négatifs

Après la phase 2, nous disposons des plus courtes distances, à condition qu'il n'existe pas de cycles négatifs. Pour détecter les cycles négatifs, nous effectuons une dernière itération supplémentaire sur toutes les arêtes.

1. Parcourez une dernière fois chaque arête (u, v) de poids w.
2. Tentez de la relâcher. Si distance[u] + w < distance[v] est TOUJOURS vrai, cela signifie que nous avons trouvé un chemin encore plus court après V - 1 arêtes.
3. C'est mathématiquement impossible pour un chemin simple. La seule explication est que nous sommes entrés dans un cycle de poids négatif qui permet de réduire la distance à l'infini. Si cela se produit, l'algorithme s'arrête et signale l'existence d'un cycle négatif.

6. Implémentation et pseudocode

La beauté de Bellman-Ford réside dans sa simplicité. L'implémentation est remarquablement directe, souvent quelques boucles imbriquées. Voici le pseudocode standard :

function BellmanFord(Graph, source):
    // Phase 1 : Initialisation
    distance = array of size |V|, filled with Infinity
    predecessor = array of size |V|, filled with Null
    distance[source] = 0

    // Phase 2 : Relâcher toutes les arêtes |V| - 1 fois
    for i from 1 to |V| - 1:
        for each edge (u, v) with weight w in Graph:
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                predecessor[v] = u

    // Phase 3 : Vérifier les cycles de poids négatif
    for each edge (u, v) with weight w in Graph:
        if distance[u] + w < distance[v]:
            return "Erreur : le graphe contient un cycle de poids négatif"

    return distance, predecessor

Ce code est indépendant du langage et se traduit facilement en Python, C++, Java ou JavaScript.

7. Analyse de la complexité en temps et en espace

Bien que Bellman-Ford soit très polyvalent, il a un coût de performance par rapport aux algorithmes gloutons.

• Complexité en temps : l'algorithme exécute une boucle V - 1 fois et, à l'intérieur, parcourt toutes les E arêtes. La complexité en temps de la phase 2 est donc O(V * E). La phase de détection de cycle coûte O(E). La complexité en temps globale est O(V * E). Dans un graphe dense où E est proche de V², la complexité approche O(V³). Cela le rend nettement plus lent que l'algorithme de Dijkstra, qui peut atteindre O(V log V + E) avec un tas de Fibonacci.
• Complexité en espace : l'algorithme n'a besoin de stocker que le tableau distance et le tableau predecessor, tous deux de taille V. Il doit aussi stocker le graphe lui-même. La complexité en espace auxiliaire est donc O(V).

En raison de sa complexité en temps de O(V * E), Bellman-Ford n'est généralement utilisé qu'en cas de nécessité, c'est-à-dire en présence de poids négatifs ou lorsque la détection de cycles négatifs est strictement requise. Pour les graphes strictement positifs, Dijkstra est le choix privilégié.

8. Applications concrètes

Bien que plus lent que Dijkstra, Bellman-Ford a des applications concrètes majeures, en particulier dans les réseaux et la finance.

Routing Information Protocol (RIP)

Dans les réseaux informatiques, les protocoles de routage déterminent comment les paquets de données circulent sur internet. L'un des protocoles les plus anciens et les plus connus, le Routing Information Protocol (RIP), est un protocole de routage à vecteur de distance qui repose largement sur une variante distribuée de l'algorithme de Bellman-Ford.

Dans cette configuration distribuée, les routeurs n'ont pas de carte complète de tout le réseau. Chaque routeur ne connaît que ses voisins immédiats. Les routeurs partagent périodiquement leurs tables de routage (leurs plus courtes distances connues vers diverses destinations) avec leurs voisins. Lorsqu'un routeur reçoit une mise à jour, il utilise l'équation de relaxation de Bellman-Ford pour mettre à jour sa propre table. Au fil du temps, cette information se propage dans le réseau, permettant à tous les routeurs de converger vers les plus courts chemins.

Détection d'arbitrage financier

L'arbitrage consiste à tirer parti d'une différence de prix entre deux marchés ou plus. Sur le marché des changes (Forex), les taux de change fluctuent. Une opportunité d'arbitrage existe si vous pouvez partir d'une devise, l'échanger contre une suite d'autres devises et vous retrouver avec plus de votre devise de départ que vous n'en aviez, sans prendre le moindre risque de marché.

Nous pouvons modéliser les taux de change comme un graphe où les nœuds sont des devises (USD, EUR, GBP, etc.) et les arêtes représentent le taux de change. Comme nous multiplions les taux au lieu de les additionner, nous pouvons prendre le logarithme négatif des taux pour transformer le problème en un problème additif. Une opportunité d'arbitrage (où le produit des taux > 1) se transforme en un cycle négatif dans notre graphe modifié. Exécuter Bellman-Ford sur ce graphe détectera ces cycles négatifs, identifiant instantanément les boucles d'arbitrage rentables pour les traders algorithmiques.

9. Ressources académiques et histoire

L'algorithme de Bellman-Ford est parfois appelé algorithme de Bellman-Ford-Moore pour reconnaître les contributions indépendantes de ces trois informaticiens :

• Alfonso Shimbel (1955) : a proposé l'algorithme à l'origine, bien qu'il ait été moins largement popularisé.
• Edward F. Moore (1959) : a publié une variante de l'algorithme dans "The shortest path through a maze" (Proceedings of the International Symposium on the Theory of Switching).
• Richard Bellman (1958) : l'a formalisé dans "On a routing problem" (Quarterly of Applied Mathematics).
• Lester Ford Jr. (1956) : a développé les concepts fondateurs dans "Network Flow Theory" (RAND Corporation Paper).

Cet algorithme a jeté les bases de la programmation dynamique, une méthode notoirement inaugurée par Richard Bellman lui-même, à l'origine d'applications étendues en mathématiques, en économie et en informatique.