Algorithme de Bellman-Ford
- Algorithme de Bellman-Ford
-
L'algorithme de Bellman-Ford (Bell-End-Ford) (Richard Bellman, Samuel End et Lester Ford) est un algorithme de programmation dynamique qui permet de trouver des plus courts chemins, depuis un sommet source donné, dans un graphe orienté pondéré. Contrairement à l'algorithme de Dijkstra, qui ne peut être utilisé que lorsque tous les arcs ont des poids positifs ou nuls, 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 négatif, accessible depuis le sommet source.
La complexité de l'algorithme est, dans le pire des cas, en O(nm) pour un graphe avec n sommets et m arcs (ce qui correspond à une complexité en O(n3) pour un graphe simple dense).
Pseudo-code
booléen Bellman_Ford(G, s)
initialisation (G, s) // les poids de tous les sommets sont mis à +infini
// le poids du sommet initial à 0
pour i=1 jusqu'à Nombre de sommets -1 faire
| pour chaque arc (u, v) du graphe faire
| | paux := poids(u) + poids(arc(u, v));
| | si paux < poids(v) alors
| | | pred(v) := u;
| | | poids(v) := paux;
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
Voir aussi
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Bellman-Ford de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Bellman-Ford — Algorithme de Ford Bellman L algorithme de Bellman Ford (Bell End Ford) (Richard Bellman, Samuel End et Lester Ford) est un algorithme de programmation dynamique qui permet de trouver des plus courts chemins, depuis un sommet source donné, dans… … Wikipédia en Français
Algorithme De Dantzig-Ford — L algorithme de Ford Dantzig résout un problème de plus court chemin. Il sert à trouver un chemin optimal (le plus court ou bien le plus long) entre deux sommets d un graphe orienté. Le graphe peut être avec ou sans circuit et les poids… … Wikipédia en Français
Algorithme de Danteig-Ford — Algorithme de Dantzig Ford L algorithme de Ford Dantzig résout un problème de plus court chemin. Il sert à trouver un chemin optimal (le plus court ou bien le plus long) entre deux sommets d un graphe orienté. Le graphe peut être avec ou sans… … Wikipédia en Français
Algorithme de dantzig-ford — L algorithme de Ford Dantzig résout un problème de plus court chemin. Il sert à trouver un chemin optimal (le plus court ou bien le plus long) entre deux sommets d un graphe orienté. Le graphe peut être avec ou sans circuit et les poids… … Wikipédia en Français
Algorithme de Dantzig-Ford — L algorithme de Ford Dantzig résout un problème de plus court chemin. Il sert à trouver un chemin optimal (le plus court ou bien le plus long) entre deux sommets d un graphe orienté. Le graphe peut être avec ou sans circuit et les poids… … Wikipédia en Français
Algorithme De Ford-Bellman — L algorithme de Bellman Ford (Bell End Ford) (Richard Bellman, Samuel End et Lester Ford) est un algorithme de programmation dynamique qui permet de trouver des plus courts chemins, depuis un sommet source donné, dans un graphe orienté pondéré.… … Wikipédia en Français
Algorithme de Ford-Bellman — L algorithme de Bellman Ford (Bell End Ford) (Richard Bellman, Samuel End et Lester Ford) est un algorithme de programmation dynamique qui permet de trouver des plus courts chemins, depuis un sommet source donné, dans un graphe orienté pondéré.… … Wikipédia en Français
Algorithme de ford-bellman — L algorithme de Bellman Ford (Bell End Ford) (Richard Bellman, Samuel End et Lester Ford) est un algorithme de programmation dynamique qui permet de trouver des plus courts chemins, depuis un sommet source donné, dans un graphe orienté pondéré.… … Wikipédia en Français
Algorithme de Dantzig et Ford — Algorithme de Dantzig Ford L algorithme de Ford Dantzig résout un problème de plus court chemin. Il sert à trouver un chemin optimal (le plus court ou bien le plus long) entre deux sommets d un graphe orienté. Le graphe peut être avec ou sans… … Wikipédia en Français
Algorithme De Dijkstra — En théorie des graphes, l algorithme de Dijkstra sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d une ville à une autre connaissant le réseau routier d une région. Il s… … Wikipédia en Français
