algorithme de Bellman-Ford

Imaginez un réseau de routes où chaque flèche porte un coût. Un coût positif représente une dépense ; un coût négatif, une remise. Pour partir d'un sommet donné au moindre coût, Bellman-Ford essaie chaque flèche plusieurs fois. Dès qu'un détour améliore un coût connu, il conserve cette nouvelle valeur.

Ces passages répétés laissent les bonnes nouvelles se propager dans tout le réseau, même lorsqu'une remise apparaît tard dans un trajet. Si un tour complet continue de diminuer le coût, l'algorithme signale une boucle de coût négatif : tourner encore permettrait de descendre sans limite.

En l'absence de cycle de poids négatif accessible depuis la source, l'algorithme de Bellman-Ford calcule les distances minimales vers tous les sommets accessibles d'un graphe pondéré orienté. Un poids peut être positif, nul ou négatif. La distance de la source vaut d'abord 0, tandis que celle de chaque autre sommet vaut provisoirement l'infini.

Pour chaque arc allant d'un sommet u vers un sommet v et portant le poids w, l'algorithme effectue une relaxation. Il remplace la distance de v lorsque le passage par u donne une valeur plus petite : $d(v)>d(u)+w\Rightarrow d(v)\leftarrow d(u)+wd(v)\; >\; d(u)+w\; \backslash Rightarrow\; d(v)\; \backslash leftarrow\; d(u)+w$. Notons |V| le nombre de sommets. L'algorithme répète l'examen de tous les arcs au plus |V| − 1 fois. Ce nombre suffit parce qu'un chemin minimal sans cycle comporte au plus |V| − 1 arcs.

Un passage supplémentaire sert de test. Si une relaxation reste possible sur un arc accessible depuis la source, un cycle de poids total négatif est accessible et aucune distance minimale finie n'existe pour les sommets que ce cycle permet ensuite d'atteindre. Sans un tel cycle, les valeurs obtenues sont les coûts des plus courts chemins ; les prédécesseurs mémorisés permettent aussi de reconstruire ces chemins.

Notons |V| le nombre de sommets du graphe pondéré. Fixez une source et initialisez sa distance à 0, toutes les autres à l'infini. Répétez au plus |V| − 1 fois le parcours de tous les arcs. Pour chaque arc u → v de poids w, appliquez $d(v)\leftarrow \min (d(v),d(u)+w)d(v)\; \backslash leftarrow\; \backslash min\backslash bigl(d(v),d(u)+w\backslash bigr)$. Vous pouvez arrêter dès qu'un parcours complet ne change aucune valeur. Enfin, parcourez encore les arcs : une nouvelle amélioration révèle un cycle de poids négatif accessible depuis la source ; sinon, les distances sont minimales.

Bellman-Ford s'applique à un graphe fini dont chaque arc possède un poids numérique, avec un sommet source fixé. Les arcs peuvent être orientés et certains poids peuvent être négatifs. Pour obtenir une distance finie vers un sommet, celui-ci doit être accessible depuis la source et ne pas être atteignable après un cycle négatif accessible. Lorsque les distances minimales sont ainsi définies, l'ordre d'examen des arcs peut changer la vitesse de propagation, mais pas le résultat final.

Un cycle négatif inaccessible depuis la source n'invalide pas les distances calculées depuis cette source. En revanche, si la source atteint un cycle de poids total −2, chaque tour réduit encore le coût : il n'existe alors pas de plus court chemin fini vers les sommets atteignables après ce cycle. Il faut signaler cette situation, corriger le modèle ou imposer une contrainte, par exemple un nombre maximal d'arcs. Si tous les poids sont non négatifs, l'algorithme de Moore-Dijkstra est généralement préférable.

Partons du sommet S. Le graphe comporte quatre sommets S, A, B et C, ainsi que quatre arcs : S → A de poids 4, S → B de poids 5, A → C de poids 3 et B → C de poids −4. La représentation du graphe permet de comparer les deux routes possibles vers C et de repérer l'arc négatif.

1. Notons d(X) la distance provisoire de S à un sommet X. Initialisons d(S) = 0 et d(A) = d(B) = d(C) = ∞.

2. Relâchons S → A puis S → B. Nous obtenons d(A) = 0 + 4 = 4 et d(B) = 0 + 5 = 5.

3. L'arc A → C propose 4 + 3 = 7. L'arc B → C propose ensuite 5 − 4 = 1 ; cette seconde valeur est plus petite, donc d(C) devient 1.

4. Un nouveau parcours ne change rien, alors l'arrêt anticipé est possible. Un dernier contrôle ne trouve aucune amélioration : il n'y a pas de cycle négatif accessible.

Le plus court chemin de S à C est S → B → C, de coût 5 + (−4) = 1. Le contrôle direct confirme que l'autre chemin, S → A → C, coûte 4 + 3 = 7.

Dans un réseau de coûts, Bellman-Ford convient lorsqu'une transition peut apporter un gain représenté par un poids négatif. Le geste consiste à relâcher chaque arc jusqu'à stabilisation, puis à contrôler qu'aucune baisse supplémentaire n'est possible.

Dans un protocole de routage à vecteur de distance, chaque nœud améliore ses estimations à partir de celles annoncées par ses voisins. On surveille alors les mises à jour persistantes, qui peuvent révéler un cycle ou une information de routage instable.

Pour choisir l'outil, inspectez d'abord les poids. S'ils sont tous non négatifs, Moore-Dijkstra évite les parcours répétés de Bellman-Ford. Si des poids négatifs sont possibles, Bellman-Ford reste adapté et ajoute la détection des cycles négatifs accessibles.

Algorithme de Moore-Dijkstra. Il calcule aussi des plus courts chemins depuis une source, mais suppose des poids non négatifs. Un seul arc de poids −4, comme B → C dans l'exemple, suffit à sortir de son domaine de garantie ; Bellman-Ford accepte cet arc.

Algorithme de Floyd-Warshall. Il cherche les distances entre toutes les paires de sommets, tandis que Bellman-Ford part d'une source donnée. Si la question porte seulement sur les trajets issus de S, Bellman-Ford ne résout pas inutilement les autres sources.

Parcours en largeur. Il minimise le nombre d'arcs dans un graphe non pondéré, pas leur coût total. Dans l'exemple, les deux trajets vers C ont deux arcs, mais leurs coûts valent 7 et 1 : le nombre d'étapes ne permet pas de trancher.

Cycle négatif accessible. Pour un graphe de |V| sommets, après |V| − 1 parcours, une distance baisse encore lors du contrôle. Il ne faut pas publier cette valeur comme un minimum : chaque tour du cycle la réduirait davantage. L'algorithme doit retourner un signal d'échec pour les sommets concernés.

Cycle négatif inaccessible. Un cycle négatif peut exister dans une composante que la source ne rejoint pas. Les distances de ses sommets restent infinies et aucune relaxation depuis cette composante ne doit déclencher une alerte pour la source étudiée.

Arête non orientée de poids négatif. La représenter par deux arcs opposés de poids −1 crée immédiatement un aller-retour de poids −2. Le symptôme est une baisse à chaque parcours. Il faut revoir le modèle plutôt que chercher un chemin minimal fini.

Coût d'exécution. Notons |V| le nombre de sommets et |E| le nombre d'arcs. Dans le pire cas, chaque arc est examiné pendant |V| − 1 parcours, soit une complexité proportionnelle à |V| × |E|. Sur un grand graphe sans poids négatif, Moore-Dijkstra est généralement plus efficace.

Graphe pondéré — Pour revoir comment des nombres portés par les arcs modélisent un coût, une durée ou une capacité.

algorithme de Moore-Dijkstra — Pour étudier l'alternative adaptée lorsque tous les poids sont non négatifs.

Trouver son chemin vite et bien — Pour replacer la recherche de chemins efficaces dans un contexte plus large.