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, aussi appelé algorithme de Bell-End-Ford[réf. nécessaire] ou algorithme de Bellman–Ford–Moore[réf. nécessaire], est un algorithme qui calcule des plus courts chemins depuis un sommet source donné dans un graphe orienté pondéré. Il porte le nom de ses inventeurs Richard Bellman, Samuel End et Lester Randolph Ford junior (publications en 1956 et 1958), et Edward Forrest Moore qui le redécouvra en 1959.

Contrairement à l'algorithme de Dijkstra, 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 strictement négatif, accessible depuis le sommet source.

La complexité de l'algorithme est en O(|S| |A|)|S| est le nombre de sommets |A| est le nombre d'arcs.

Description[modifier | modifier le code]

L'algorithme de Bellman-Ford utilise le principe de la programmation dynamique. On décrit ici un algorithme qui retourne les distances d'un sommet source donné à tous les autres sommets. Supposons que le graphe ne contienne pas de cycles de poids négatifs. Les sous-problèmes sont :

  •  d[t, k] est la distance du sommet source s à t avec un chemin qui contient au plus k arcs.

On a :

  •  d[t, 0] = +\infty pour t ≠ s et d[s, 0] = 0 ;
  •  d[t, k] = min\left[d[t, k-1], min_{\text{arc } (u, t)} (d[u, k-1] + poids(u, t))\right].

L'algorithme calcule les valeurs  d[t, k] par valeur de k croissante. La distance de s à t est  d[t, |S|-1].

Pseudo-code[modifier | modifier le code]

On donne d'abord une version en pseudo-code qui utilise directement la relation de récurrence donné dans la section précédente.

 fonction Bellman_Ford(G, s) 
   pour chaque sommet u du graphe
   |        d[u, 0] = +∞
   d[s, 0] = 0

   pour k = 1 jusqu'à Nombre de sommets - 1 faire
    |      pour sommet t faire
    |      |    d' := d[t, k-1]
    |      |    pour chaque arc (u, t) du graphe faire
    |      |    |      d' := min(d', d[u, k-1] + poids(u, t))
    |      |    d[t, k] = d'

   retourner d[., |S|-1]

En fait, on peut donner une version qui calcule en place les distances :

 fonction Bellman_Ford(G, s) 
   pour chaque sommet u du graphe
   |        d[u] = +∞
   d[s] = 0

   pour k = 1 jusqu'à Nombre de sommets - 1 faire
    |    pour chaque arc (u, t) du graphe faire
    |      |    d[t] := min(d[t], d[u] + poids(u, t))

   retourner d

On peut détecter la présence d'un cycle de poids négatifs de la façon suivante : il y a un cycle de poids négatifs si et seulement si un nouveau tour de boucle ferait diminuer une distance. Ainsi, à la fin de l'algorithme, on fait :

   pour chaque arc (u, t) du graphe faire
    |    si d[u] + poids(u, t) < d[t] alors
    |         afficher "il existe un cycle absorbant"

Complexité[modifier | modifier le code]

La complexité de l'algorithme est en O(|S| |A|)|S| est le nombre de sommets |A| est le nombre d'arcs. Cela correspond à une complexité en O(|S|^3) pour un graphe simple dense.

Améliorations[modifier | modifier le code]

On peut arrêter l'exécution de la boucle principe lorsque les distances sont inchangées comme le montre le pseudo-code suivant :

 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

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

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

Bibliographie[modifier | modifier le code]

Sources originales[modifier | modifier le code]

  • (en) Richard Bellman, « On a routing problem », Quarterly of Applied Mathematics, vol. 16,‎ , p. 87–90
  • (en) Lester R. Ford Jr., Network Flow Theory, Santa Monica, California, RAND Corporation, coll. « Paper P-923 »,‎ (lire en ligne)
  • (en) Moore, Edward F. (1959). « The shortest path through a maze » in Proc. Internat. Sympos. Switching Theory 1957, Part II. Harvard Univ. Press : 285–292, Cambridge, Mass.: Harvard Univ. Press. 
  • (en) Jin Y. Yen, « An algorithm for finding shortest routes from all source nodes to a given destination in general networks », Quarterly of Applied Mathematics, vol. 27,‎ , p. 526–530
  • (en) Bannister, M. J.; Eppstein, D. (2012) « Randomized speedup of the Bellman–Ford algorithm » in Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan. : 41–47. 

Livres en français[modifier | modifier le code]

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

Voir aussi[modifier | modifier le code]