Algorithme de Ford-Bellman

Le problème des plus courts chemins à partir d’une origine n’a de solution que s’il n’existe pas de circuit absorbant atteignable. L’algorithme de Bellman-Ford vérifie qu’il n’existe pas de circuit absorbant atteignable à partir de s. Si c’est le cas, il retourne les plus courts chemins à partir de s. L’algorithme de Bellman-Ford est un algorithme de programmation dynamique gourmand qui calcule les chemins les plus courts de taille croissante. Il convient à n’importe quel graphe.

Conditions.

  • Cas général

Au départ, la distance est initialisée à 0 pour l’origine et à l’infini pour les autres sommets.

ford1

On va examiner tous les arcs et améliorer si possible la valeur des chemins. La nouvelle valeur pour chaque sommet est la distance minimale de tous les chemins de taille k-1 auxquels on rajoute les arêtes entrant dans le sommet. Comme il peut y avoir des circuits, il faut recommencer.

ford2

ford3

Pour des raisons pratiques, la résolution du l’algorithme de Ford ne retourne qu’un vecteur. Ce qui correspond à une colonne courante du tableau présenté.

Optimalité.

Le chemin le plus court de l’origine à lui-même est de 0. Puis les chemins de taille 1 sont calculés de telle sorte que nous ne gardons que le plus court chemin de l’origine à tout autre sommet.

l’algorithme calcule les plus courts chemins des chemins de taille k (pour l’itération k) à partir des plus courts chemins des chemins de taille k-1, il est donc optimal quelle que soit l’itération d’arrêt de l’algorithme.

S’il n’y a pas ce circuit absorbant, un plus court chemin est nécessairement élémentaire. On est donc sûr qu’un plus court chemin doit alors être trouvé en au plus n-1 étapes de l’itération. Si une valeur de D est améliorée, c’est qu’il y a un circuit absorbant.

pour chaque sommet u du graphe
   d[u, 0] = +∞
d[s, 0] = 0
pour k = 1 jusqu'à Nombre de sommets - 1 faire
    pour chaque arc (u, v) du graphe faire
        d[v, k] := min(d[v, k-1], d[u, k-1] + poids(u, v))
    fin
fin
retourner d

 

Exemple

Prenons pour exemple le graphe suivant :

bellman1

Prenons le noeud 5 comme source, puis on initialise les autres distances à l’infini. Le vecteur π représente les prédécesseurs.

bellman2

Itération 1: Les arcs (u5,u2) et (u5,u4) sont relaxés, on met à jour les distances et les prédécesseurs.

bellman3

Itération 2: Les arcs (u2,u1), (u4,u2) et (u4,u3) sont relaxés, on met à jour les distances aux noeuds 1, 2, et 4. Notons que (u4,u2) trouve un plus court chemin vers 2 en passant par le noeud 4.

bellman4

Itération 3: Les arcs (u2,u1) sont relaxés (car on a trouvé un chemin plus court pour aller au noeud 2 dans la dernière itération).

bellman5

Itération 4: Aucun arc n’est relaxé.

bellman6

Les chemins les plus courts partant du noeud 5 sont :

bellman7

L’algorithme se présente sous la forme d’un tableau comme ci-dessous :

Iteration 1 2 3 4 5
0 inf inf inf inf 0
1 inf 4(5) inf 2(5) 0
2 7(2) 3(4) 3(4) 2(5) 0
3 6(2) 3(4) 3(4) 2(5) 0
4 6(2) 3(4) 3(4) 2(5) 0

Les distances en rouge montre les noeuds qui ont subi un changement dans l’itération courante. Pour l’itération suivante il faut donc relaxé les arcs provenant de ces noeuds. L’algorithme s’arrête lorsqu’il n’y a plus de changement.

Publicités