| Découvreurs ou inventeurs |
Richard Bellman (), L. R. Ford, Jr. (), Edward F. Moore () |
|---|---|
| Problèmes liés | |
| Structure des données | |
| À l'origine de |
| Pire cas | |
|---|---|
| Meilleur cas |
| Pire cas |
|---|
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 :
On a :
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 à . La valeur null signifie qu'aucun prédécesseur n'a pour l'instant été assigné à .
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 ) 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 d[v] > d[u] + poids(u, v) alors
| afficher "il existe un cycle absorbant"
La complexité de l'algorithme est en où est le nombre de sommets et est le nombre d'arcs. Cela correspond à une complexité en pour un graphe simple dense.
La démonstration de la correction de l'algorithme peut se faire par récurrence :
Lemme. Après répétitions de la boucle principale :
Preuve. Pour le cas , correspondant à la première exécution de la boucle for, alors, d'une part, et, pour tout sommet , , prouvant le premier point et, d'autre part, est le seul sommet tel qu'il existe un chemin d'au plus 0 arêtes le reliant à .
Pour le cas non nul quelconque, alors :
Le lemme est donc démontré. Il s'ensuit que la longueur est la longueur d'un plus court chemin de à , ce qui prouve la correction de l'algorithme de Bellman-Ford dans le cas où n'a pas de cycle de poids négatif.
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 fois. La complexité dans le pire cas est inchangée. Yen 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.
Une autre amélioration par Bannister & Eppstein 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 Ef tantôt dans Eb). Avec une permutation aléatoire comme ordre total, l'espérance du nombre d'itérations de la boucle principale est d'au plus .
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 diagrammes de décision binaire.
Dans les réseaux informatiques, l'algorithme de Bellman-Ford est utilisé pour déterminer le cheminement des messages, à travers le protocole de routage RIP. 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,.