algorithme de Bellman-Ford

Also known as Bellman–Ford–Moore algorithm, Bellman-Ford equation, distance-vector routing algorithm

calcul des plus courts chemins depuis un sommet source donné dans un graphe orienté pondéré

Key facts

Class: Single-source shortest path problem (for weighted directed graphs)
Data structure: Graph
Worst case performance: Θ ( | V | | E | ) {\displaystyle \Theta (|V||E|)}
Best case performance: Θ ( | E | ) {\displaystyle \Theta (|E|)}
Worst case space complexity: Θ ( | V | ) {\displaystyle \Theta (|V|)}

via Wikipedia infobox

Wikidata facts

Image: Bellman–Ford algorithm example.gif

Show 1 more fact

Commons category: Bellman–Ford algorithm

Sources (2)

Article · Français

L'algorithme de Bellman-Ford, aussi appelé algorithme de Bellman–Ford–Moore, 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 où est le nombre de sommets est le nombre d'arcs.

Abstract from DBpedia / Wikipedia · CC BY-SA