Voir la source de Algorithme de Bellman-Ford

{{Voir paronymes|Algorithme de Ford-Fulkerson}}
{{Infobox Algorithme}}

L''''algorithme de Bellman-Ford''', aussi appelé '''algorithme de Bellman–Ford–Moore'''<ref>Par exemple dans {{Citation|On the optimality of Bellman–Ford–Moore shortest path algorithm}}, Note de Stasys Jukna et Georg Schnitger, parue dans ''Theoretical Computer Science'' 628 (2016) 101–109.</ref>, est un [[Algorithmique|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]] et [[Lester Randolph Ford junior]] (publications en 1956 et 1958), et de [[Edward F. Moore|Edward Forrest Moore]] qui le redécouvrit 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 (graphe)|circuit absorbant]], c'est-à-dire de poids total strictement négatif, accessible depuis le sommet source.

La [[complexité en temps|complexité]] de l'algorithme est en <math>O(|S| |A|)</math> où <math>|S|</math> est le nombre de sommets <math>|A|</math> est le nombre d'arcs.

== Description ==
L'algorithme de Bellman-Ford calcule, étant donnés un graphe <math>G = (S, A)</math> sans cycle de poids négatif et un sommet source <math>s \in S</math>, un plus court chemin de <math>s</math> à chaque sommet de <math>G</math>. Il permet en plus de trouver un tel chemin en retournant les prédécesseurs de chaque sommet dans un tel chemin. En outre, il permet de détecter les cas où il existe un cycle de poids négatif et donc dans lesquels il n'existe pas nécessairement de plus court chemin entre deux sommets.

L'algorithme utilise le principe de la [[programmation dynamique]] (il est traité dans le chapitre portant sur la programmation dynamique dans certains livres d'algorithmique<ref>{{Lien web|titre=Lecture Slides for Algorithm Design by Jon Kleinberg And Éva Tardos|url=http://www.cs.princeton.edu/~wayne/kleinberg-tardos/|site=www.cs.princeton.edu|consulté le=15 mars 2016}}.</ref>). Les sous-problèmes sont :
* <math> d[t, k]</math> est la distance du sommet source s à t avec un chemin qui contient au plus k arcs.
On a :
* <math> d[t, 0] = +\infty</math> pour <math> t \neq s</math> et <math> d[s, 0] = 0</math> ;
* <math> d[t, k] = min\left[d[t, k-1], min_{\text{arc } (u, t)} (d[u, k-1] + poids(u, t))\right]</math>.
L'algorithme calcule les valeurs  <math> d[t, k]</math> par valeur de k croissante. La distance de s à t est <math> d[t, |S|-1]</math>.

== Pseudo-code ==
L'algorithme de Bellman-Ford s'écrit donc en utilisant directement la [[Suite définie par récurrence|relation de récurrence]] donnée dans la section précédente<ref name=":0" />.
  '''fonction''' Bellman-Ford(G = (S, A), poids, s)
    '''pour''' u '''dans''' S '''faire'''
    |       d[u] = +∞
    |       pred[u] = null
    d[s] = 0
    //''Boucle principale''
    '''pour''' k = 1 '''jusqu'à''' taille(S) - 1 '''faire'''
     |      '''pour chaque''' arc (u, v) du graphe '''faire'''
     |      |    '''si'''<nowiki> d[u] + poids(u, v) < d[v] </nowiki>'''alors'''
     |      |    |    d[v] <nowiki>:= d[u] + poids(u, v)</nowiki>
     |      |    |    pred[v]:= u

    '''retourner''' d, pred
À l'issue de l'exécution de cet algorithme, <math>d[u]</math> représente la longueur d'un plus court chemin de <math>s</math> à <math>u</math> dans <math>G</math>, alors que <math>pred[u]</math> représente le prédécesseur de <math>u</math> dans un plus court chemin de <math>s</math> à <math>u</math>. La valeur null signifie qu'aucun prédécesseur n'a pour l'instant été assigné à <math>pred[u]</math>.

L'algorithme de Bellman-Ford n'est correct que dans un graphe sans cycle de poids négatif. On peut détecter la présence d'un tel cycle (à condition qu'il soit accessible depuis le sommet <math>s</math>) de la façon suivante : il y a un cycle de poids négatif si et seulement si un nouveau tour de boucle fait diminuer une distance. Ainsi, à la fin de l'algorithme, on fait :
    '''pour chaque''' arc (u, v) du graphe '''faire'''
     |    '''si'''<nowiki> d[v] > d[u] + poids(u, v) </nowiki>'''alors'''
     |         afficher "il existe un cycle absorbant"

== Complexité ==
La [[complexité en temps|complexité]] de l'algorithme est en <math>O(|S| |A|)</math> où <math>|S|</math> est le nombre de sommets et <math>|A|</math> est le nombre d'arcs. Cela correspond à une complexité en <math>O(|S|^3)</math> pour un [[Graphe dense|graphe simple dense]]<ref name=":0" />.

== Preuve de la correction ==
La démonstration de la correction de l'algorithme peut se faire par [[Raisonnement par récurrence|récurrence]] :

'''Lemme.''' Après <math>i</math> répétitions de la boucle principale :

* Si <math>d[u] \neq +\infty</math>, alors <math>d[u]</math> est le poids d'un chemin de <math>s</math> à <math>u</math> ;
* S'il existe un chemin de <math>s</math> à <math>u</math> d'au plus <math>i</math> arêtes, alors <math>d[u]</math> est au plus la longueur du plus court chemin de <math>s</math> à <math>u</math> comprenant au plus <math>i</math> arêtes.

'''Preuve.''' Pour le cas <math>i = 0</math>, correspondant à la première exécution de la boucle <code>for</code>, alors, d'une part, <math>d[s] = 0</math> et, pour tout sommet <math>u \neq s</math>, <math>d[u] = +\infty</math>, prouvant le premier point et, d'autre part, <math>s</math> est le seul sommet tel qu'il existe un chemin d'au plus 0 arêtes le reliant à <math>s</math>.

Pour le cas <math>i</math> non nul quelconque, alors :

* D'une part, supposons <math>d[v]</math> soit mis à jour avec <math>d[v] := d[u] + \text{poids}(u, v)</math>. Alors, comme <math>d[u] \neq +\infty</math> (car sinon, la mise à jour n'aurait pas lieu),<math>d[u]</math> représente le poids d'un chemin de <math>s</math> à <math>u</math>. Donc, par construction, <math>d[v]</math> est le poids d'un chemin de <math>s</math> à <math>v</math> ;
* D'autre part, soit <math>C</math>, un plus court chemin de <math>s</math> à <math>v</math> d'au plus <math>i</math> arêtes. Soit <math>u</math> le dernier sommet avant <math>v</math> sur ce chemin. Soit <math>C'</math>, le sous-chemin de <math>C</math> allant de <math>s</math> à <math>u</math>. Alors, par induction, <math>C'</math> est un plus court chemin de <math>s</math> à <math>u</math> d'au plus <math>i - 1</math> arêtes (en effet, sinon, il existe un chemin strictement plus court de <math>s</math> à <math>u</math>. En y ajoutant l'arête de <math>u</math> à <math>v</math>, on trouve un chemin strictement plus court que <math>C</math> allant de <math>s</math> à <math>v</math>, ce qui est contradictoire avec la définition de <math>C</math>). Alors, par hypothèse de récurrence, à l'issue de l'itération <math>i - 1</math>, <math>d[u]</math> était au plus la longueur d'un plus court chemin de <math>s</math> à <math>u</math> d'au plus <math>i - 1</math> arêtes. Ainsi, à la <math>i</math>-ème [[itération]], <math>d[v] \leq d[u] + \text{poids}(u, v)</math>, en raison de la structure de l'algorithme. Or, cette dernière longueur est au plus la longueur d'un plus court chemin de <math>s</math> à <math>v</math>.

Le lemme est donc démontré. Il s'ensuit que la longueur <math>d[u]</math> est la longueur d'un plus court chemin de <math>s</math> à <math>u</math>, ce qui prouve la correction de l'algorithme de Bellman-Ford dans le cas où <math>G</math> n'a pas de cycle de poids négatif<ref name=":0" />.

== Améliorations ==
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 <math>|S|-1</math> fois. La complexité dans le pire cas est inchangée. Yen<ref>{{MathSciNet|0253822}}.</ref> 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.
# 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.
# La seconde amélioration de Yen consiste à choisir un ordre total arbitraire < sur les sommets puis à partitionner l'ensemble des arcs en deux sous-ensembles disjoints. Le premier sous-ensemble ''E<sub>f</sub>'' contient les arcs (u, t) avec u < t et le second, ''E<sub>b</sub>'', 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 ''E<sub>f</sub>''. Puis on visite les sommets u dans l'ordre décroissant >. On relâche les arcs (u, t) dans ''E<sub>b</sub>''. 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 ''E<sub>f</sub>''  et un dans ''E<sub>b</sub>''. Cette amélioration réduit le nombre d'itérations de la boucle principale de <math>|S|-1</math> à <math>\frac{|S|}2</math>.
Une autre amélioration par Bannister & Eppstein<ref>{{Article|prénom1=Michael J.|prénom2=David|nom1=Bannister|nom2=Eppstein|titre=Randomized Speedup of the Bellman-Ford Algorithm|périodique=Proceedings of the Meeting on Analytic Algorithmics and Combinatorics|série=ANALCO '12|éditeur=Society for Industrial and Applied Mathematics|date=1 janvier 2012|lire en ligne=http://dl.acm.org/citation.cfm?id=2790395.2790401|consulté le=15 mars 2016|pages=41–47}}.</ref> 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 ''E<sub>f</sub>''  tantôt dans ''E<sub>b</sub>''). Avec une permutation aléatoire comme ordre total, l'espérance du nombre d'itérations de la boucle principale est d'au plus <math>\frac{|S|}3</math>.

En 1993, Bahar {{et al.}} ont donné une implémentation de l'algorithme de Bellman-Ford pour des graphes représentés symboliquement à l'aide d'une [[structure de données]] appelée Algebraic Decision Diagrams (ADD), qui est une généralisation des [[Diagramme de décision binaire|diagrammes de décision binaire]]<ref>{{Article|langue=|auteur1=|prénom1=R. Iris|nom1=Bahar|prénom2=Erica A.|nom2=Frohm|prénom3=Charles M.|nom3=Gaona|prénom4=Gary D.|nom4=Hachtel|titre=Algebraic decision diagrams and their applications|périodique=ICCAD '93 Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design|éditeur=IEEE Computer Society Press|date=1993-11-07|isbn=0818644907|issn=|lire en ligne=http://dl.acm.org/citation.cfm?id=259794.259826|consulté le=2018-02-09|pages=188–191}}</ref>.

== Utilisations ==
Dans les [[Réseau informatique|réseaux informatiques]], l'algorithme de Bellman-Ford est utilisé pour déterminer le cheminement des messages, à travers le protocole de [[routage]] [[Routing Information Protocol|RIP]]{{RFC|1058|ref=oui}}. On peut utiliser l'algorithme de Bellman-Ford pour résoudre un problème de [[programmation linéaire]] où les contraintes 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 cycles de poids négatif<ref>{{Article|prénom1=Robert|nom1=Shostak|titre=Deciding Linear Inequalities by Computing Loop Residues|périodique=J. ACM|volume=28|date=1981-10-01|issn=0004-5411|doi=10.1145/322276.322288|lire en ligne=http://doi.acm.org/10.1145/322276.322288|consulté le=2016-04-22|pages=769–779}}.</ref>{{,}}<ref name=":0">{{Ouvrage|langue=fr|auteur1=Thomas H. Cormen, Charles Leiserson, Ronald Rivest et Clifford Stein|titre=Introduction à l'algorithmique : Cours et exercices|passage=Chapitre 24 : Plus courts chemins à origine unique|éditeur=[[Éditions Dunod|Dunod]]|année=2009|isbn=}}.</ref>.

== Notes et références ==
{{Références}}

== Bibliographie ==

=== Sources originales ===
* {{article|langue=en
 |nom = Bellman|prénom = Richard|lien auteur = Richard Bellman|mr = 0102435|journal = Quarterly of Applied Mathematics|pages = 87–90|titre = On a routing problem|volume = 16|année = 1958}}
* {{Ouvrage|langue=en|prénom1=Lester R.|nom1=Ford Jr.|lien auteur1=Lester Randolph Ford junior|titre=Network Flow Theory|lieu=Santa Monica, California|éditeur=RAND Corporation|collection=Paper P-923|date=14 août 1956|isbn=|lire en ligne=http://www.rand.org/pubs/papers/P923.html}}
* {{lien conférence|langue=en
 |nom = Moore|prénom = Edward F.|lien auteur = Edward F. Moore |titre = The shortest path through a maze |lieu = Cambridge, Mass.|mr = 0114710|pages = 285–292|éditeur = Harvard Univ. Press|conférence = Proc. Internat. Sympos. Switching Theory 1957, Part II|année = 1959 <!-- paramètre non supporté |ref = harv--> }}
* {{article|langue=en
 |nom = Yen|prénom = Jin Y.|mr = 0253822|journal = Quarterly of Applied Mathematics|pages = 526–530|titre = An algorithm for finding shortest routes from all source nodes to a given destination in general networks|volume = 27|année = 1970}}
* {{lien conférence|langue=en|titre = Randomized speedup of the Bellman–Ford algorithm|prénom1 = M. J.|nom1 = Bannister|prénom2 = D.|nom2 = Eppstein|lien auteur2 = David Eppstein|arxiv = 1111.5414|conférence = Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan|année = 2012|pages = 41–47|url = http://siam.omnibooksonline.com/2012ANALCO/data/papers/005.pdf|format=pdf <!-- paramètre non supporté |ref = harv--> }}

=== Livres en français ===
* {{Ouvrage|prénom1=Michel|nom1=Gondran|lien auteur1=Michel Gondran|prénom2=Michel|nom2=Minoux|titre=Graphes et algorithmes|éditeur=[[Eyrolles|Éditions Eyrolles]]|collection=Études et recherches d'Électricité de France|année=1979|réimpression=1984, 1995, 2009 chez Lavoisier, {{4e}} ed.|pages totales=548|isbn=|titre chapitre=2 - Le problème du plus court chemin}}

== Voir aussi ==
{{Autres projets|wiktionary=algorithme de Bellman-Ford}}
* [[Algorithme de Dijkstra]]
* [[Algorithme de Floyd-Warshall]]

{{Palette|Algorithmes sur les graphes}}
{{Portail|informatique théorique}}

[[Catégorie:Algorithme de la théorie des graphes|Ford-Bellman]]
[[Catégorie:Algorithme de recherche]]
[[Catégorie:Recherche opérationnelle]]