Algorithme de Bellman-Ford

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. L'algorithme de Bellman-Ford calcule, étant donnés un graphe sans cycle de poids négatif et un sommet source , un plus court chemin de à chaque sommet de . 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). Les sous-problèmes sont : est la distance du sommet source s à t avec un chemin qui contient au plus k arcs. On a : pour et ; L'algorithme calcule les valeurs par valeur de k croissante. La distance de s à t est . L'algorithme de Bellman-Ford s'écrit donc en utilisant directement la relation de récurrence donnée dans la section précédente. 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 d[u] + poids(u, v) < d[v] alors | | | d[v] := d[u] + poids(u, v) | | | pred[v]:= u retourner d, pred À l'issue de l'exécution de cet algorithme, représente la longueur d'un plus court chemin de à dans , alors que représente le prédécesseur de dans un plus court chemin de à .