Algorithme de Ford-Bellman

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 Ford-Bellman 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 Ford-Bellman 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.

plus court chemin algorithme de Ford-Bellman ford

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.

plus court chemin algorithme de Ford-Bellman ford
algorithme de Ford-Bellman plus court chemin

Pour des raisons pratiques, la résolution du l’algorithme de Ford-Bellman 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 :

plus court chemin algorithme de Ford-Bellman ford

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

plus court chemin algorithme de Ford-Bellman ford

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

plus court chemin algorithme de Ford-Bellman ford

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.

plus court chemin algorithme de Ford-Bellman ford

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).

plus court chemin algorithme de Ford-Bellman ford

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

plus court chemin algorithme de Ford-Bellman ford

Les chemins les plus courts partant du noeud 5 sont :

plus court chemin algorithme de Ford-Bellman ford

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

Iteration12345
0infinfinfinf0
1inf4(5)inf2(5)0
27(2)3(4)3(4)2(5)0
36(2)3(4)3(4)2(5)0
46(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.

Partager
fr_FRFR
%d blogueurs aiment cette page :