Algorithme de Bellman-Ford

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Algorithme de Ford-Fulkerson.

L'algorithme de Bellman-Ford (Bell-End-Ford) (Richard Bellman, Samuel End et Lester Randolph Ford junior (de)) est un algorithme qui permet de trouver des plus courts chemins, depuis un sommet source donné, dans un graphe orienté pondéré.

Comme l'algorithme de Dijkstra, il utilise le principe de la programmation dynamique. Mais contrairement à ce dernier l'algorithme de Bellman-Ford autorise la présence de certains arcs de poids négatif et permet de détecter l'existence d'un circuit absorbant, c'est-à-dire de poids total négatif, accessible depuis le sommet source.

La complexité de l'algorithme est, dans le pire des cas, en O(n m) pour un graphe avec n sommets et m arcs (ce qui correspond à une complexité en O(n^3) pour un graphe simple dense).

Description[modifier | modifier le code]

Pseudo-code[modifier | modifier le code]

 booléen Bellman_Ford(G, s) 
   initialisation (G, s)  /*
                          ** les poids de tous les sommets sont mis à +infini 
                          ** le poids du sommet initial à 0
                          ** nouveauPoids du sommet initial à 0, les autres à -1
                          ** precedent initialise a +infini
                          */ 
   pour i=1 jusqu'à Nombre de sommets - 1 faire
    |    poidsInchangés := vrai
    |    pour chaque sommet u du graphe dont nouveauPoids(u) = i - 1
    |     |    pour chaque arc (u, v) du graphe faire
    |     |    nouveau_poids := poids(u) + poids(arc(u, v)); 
    |     |     |   si nouveau_poids < poids(v) alors
    |     |     |    |    precedent(v) := u; 
    |     |     |    |    poids(v) := nouveau_poids; 
    |     |     |    |    nouveauPoids(v) := i
    |     |     |    |    poidsInchangés := faux;
    |     si poidsInchangés = vrai alors sortir de la boucle
   pour chaque arc (u, v) du graphe faire
    |    si poids(u) + poids(arc(u, v)) < poids(v) alors
    |         retourner faux  // il existe un cycle absorbant
   retourner vrai

Utilisation[modifier | modifier le code]

Dans les réseaux informatiques, l'algorithme de Bellman-Ford est utilisé pour déterminer le cheminement des messages, à travers le protocole de routage RIP[1].

Améliorations[modifier | modifier le code]

Notes et références[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Michel Gondran et Michel Minoux, Graphes et algorithmes, Éditions Eyrolles, coll. « Études et recherches d'Électricité de France »,‎ 1979 (réimpr. 1986), 548 p., « 2 - Le problème du plus court chemin »

Voir aussi[modifier | modifier le code]