Algorithme de Bellman-Ford

Cet article possède un paronyme, voir Algorithme de Ford-Fulkerson.

Algorithme de Bellman-Ford

Découvreurs ou inventeurs	Richard Bellman (1958), L. R. Ford, Jr. (1956), Edward F. Moore (1957)
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (en), concept mathématique (en)
Structure des données	Graphe
À l'origine de	Routing Information Protocol[1], Babel[2]

Complexité en temps

Pire cas	${\displaystyle \Theta (|V||E|)}$
Meilleur cas	${\displaystyle \Theta (|E|)}$

Complexité en espace

Pire cas	${\displaystyle \Theta (|V|)}$

modifier - modifier le code - modifier Wikidata

L'algorithme de Bellman-Ford, aussi appelé algorithme de Bellman–Ford–Moore^[3], 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 et Lester Randolph Ford junior (publications en 1956 et 1958), et de 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 absorbant, c'est-à-dire de poids total strictement négatif, accessible depuis le sommet source.

La complexité de l'algorithme est en ${\displaystyle O(|S||A|)}$ où ${\displaystyle |S|}$ est le nombre de sommets ${\displaystyle |A|}$ est le nombre d'arcs.