Algorithme de Bellman-Ford

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Algorithme de Ford-Bellman)
Aller à : navigation, rechercher
image illustrant l’informatique théorique
Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 (il est traité dans le chapitre portant sur la programmation dynamique dans certains livres d'algorithmique[1]). 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 principale lorsque les distances sont inchangées. Le corps de la boucle principale est alors exécuté moins de |S|-1 fois. La complexité dans le pire cas est inchangée. Yen[2] a décrit deux améliorations à l'algorithme de Bellman-Ford qui ne changent pas la complexité dans le pire cas mais qui le rend plus rapide en pratique.

  1. La première amélioration réduit le nombre de relaxations. Si d[u] n'a pas été modifié depuis une relaxation d'un arc (u, t), alors il n'y a pas besoin de relâcher les arcs (u, t) une deuxième fois. Ainsi, comme le nombre de sommets avec la distance correcte augmente au cours de l'algorithme, le nombre d'arcs à relâcher diminue à chaque itération. On gagne un facteur constant sur la complexité pour des graphes denses.
  2. La seconde amélioration de Yen choisit un ordre total arbitraire < sur les sommets puis à partitionner l'ensemble des arcs en deux sous-ensembles disjoints. Le premier sous-ensemble Ef contient les arcs (u, t) avec u < t et le second, Eb, contient les arcs (u, t) avec u > t. La boucle pour chaque arc (u, t) du graphe faire s'effectue de la façon suivante. Chaque sommet u est visité par ordre croissant <. Puis on relâche chaque arc (u, t) dans Ef. Puis on visite les sommets u dans l'ordre décroissant >. On relâche les arcs (u, t) dans Eb. Chaque itération de la boucle principale (sauf la première) ajoute au moins deux arcs dont les sommets ont des distances correctes, l'un dans Ef et un dans Eb. Cette amélioration réduit le nombre d'itérations de la boucle principale de |S|-1 à \frac{|S|}2.

Une autre amélioration par Bannister & Eppstein[3] consiste à remplacer l'ordre total sur les sommets de la seconde amélioration de Yen par une permutation aléatoire. Ainsi, le pire cas de l'amélioration de Yen arrive peu souvent (le fait que les arcs d'un plus court chemin sont tantôt dans Ef tantôt dans Eb). Avec une permutation aléatoire comme ordre total, l'espérance du nombre d'itérations de la boucle principale est d'au plus \frac{|S|}3 .

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[4]. On peut utiliser l'algorithme de Bellman-Ford pour résoudre un problème de programmation linéaire où les contraintes qui sont des différences. Par exemple ː x - y ≤ 5, y - t ≤ 10, etc. Plus précisément, un tel système a une solution si et seulement si le graphe associé n'a pas de cycle de poids négatifs[5],[6].

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

  1. « Lecture Slides for Algorithm Design by Jon Kleinberg And Éva Tardos », sur www.cs.princeton.edu (consulté le 15 mars 2016)
  2. « MR: Matches for: MR=253822 », sur www.ams.org (consulté le 15 mars 2016)
  3. Michael J. Bannister et David Eppstein, « Randomized Speedup of the Bellman-Ford Algorithm », Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, Society for Industrial and Applied Mathematics, série ANALCO '12,‎ , p. 41–47 (lire en ligne)
  4. RFC 1058
  5. Robert Shostak, « Deciding Linear Inequalities by Computing Loop Residues », J. ACM, vol. 28,‎ , p. 769–779 (ISSN 0004-5411, DOI 10.1145/322276.322288, lire en ligne)
  6. E. Leiserson, Clifford Stein, Ronald Rivest et Thomas H. Cormen, Algorithmique: cours avec 957 exercices et 158 problèmes, Dunod,‎

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]