Algorithme de Bellman-Ford

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Algorithme de Ford-Bellman)
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 de programmation dynamique qui permet de trouver des plus courts chemins, depuis un sommet source donné, dans un graphe orienté pondéré. Contrairement à l'algorithme de Dijkstra, qui ne peut être utilisé que lorsque tous les arcs ont des poids positifs ou nuls, 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).

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].

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

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]