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.

Conditions.

  • Cas général

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

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.

bfex

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
Publicités