Algorithme de Ford-Bellman

Fonctionnalités de l'algorithme de Ford-Bellman

Nous retrouvons cet algorithme sous le nom de Ford-Bellman, ou aussi Bellman-Ford.

  • Ford-Bellman est un algorithme de recherche de chemin extrême.
  • Ford-Bellman est utilisé sur des graphes pondérés1
  • Nous pouvons utiliser l'algorithme de Ford-Bellman sur des graphes aux pondérations quelconques, et des graphes avec circuits ou sans circuits.
  • L'algorithme de Ford-Bellman nous permet de détecter un circuit absorbant. Dans ce cas, nous ne pouvons toutefois pas déterminer de chemin optimal.

Contents Haut

Caractéristiques de l'algorithme de Ford-Bellman

Nous sommes à la recherche du chemin le plus court. Cela signifie que la somme des poids des arcs du chemin sélectionné doit être le plus faible possible.

L'algorithme de Ford-Bellman est différent des algorithmes que nous avons vu jusqu'à présent (Bellman-Kalaba, Moore-Dijkstra), qui nous permettaient une exploration progressive, sans back-tracking2.

Ford-Bellman remet en cause les résultats précédents car il accepte les circuits et les pondérations quelconques (alors que Moore-Dijkstra, s'il accepte les circuits, n'accepte pas de pondérations négatives).
La présence de pondérations négatives dans un graphe avec circuits ne permet plus de marquer définitivement un sommet, car le passage par un arc négatif décroît la valeur du chemin à chaque passage par ce circuit.

Principe de relâchement

Le principe général est le même que pour le relâchement dans Moore-Dijkstra : nous utiliserons une valeur tellement haute3 que tout au long de l'exécution de l'algorithme nous ne devrons jamais définir de nouvelles valeurs qui lui soient égales ou supérieures.

Nous diminuerons (relâcherons) cette valeur à chaque fois que nous trouverons une valeur plus intéressante.

Principe d'ajustement progressif

Les résultats ne sont pas définitifs, et sont remis en cause à chaque itération si un chemin plus court permet d'atteindre un sommet.

A chaque passage dans la boucle, nous devons trouver pour le sommet x les arcs incidents à x vers l'intérieur4, arcs (y -> x).

Nous calculons ensuite le coût (le poids) nécessaire pour atteindre x en passant par y. Ce coût (r -> y -> x) est calculé en ajoutant à la pondération de l'arc (y -> x), le poids du chemin de la racine vers y.

Si le poids minimum calculé pour x et tout y possible est inférieur à l'ancien poids (r -> x), nous devons remplacer ce poids par la nouvelle valeur, et mémoriser (par l'étiquette) que y est le meilleur précédent actuel pour atteindre x car nous vennons de découvrir un chemin plus court (de poids inférieur) de la racine vers x.

Contents Haut

Code de l'algorithme de Ford-Bellman

Nous pouvons décomposer notre algorithme en deux phases : une phase d'initialisation des valeurs, et une phase d'exécution qui décrit ce qui se passe lorsque l'algorithme est exécuté.

Variables

Dans cette approche, nous utilisons des collections indexées (par exemple des tableaux) pour maintenir les différentes informations relatives aux états de chaque objet Sommet. Dans une approche "orienté-objet", nous pouvons maintenir ces informations par exemple dans l'objet Sommet lui même.

  • verticesLabels est le tableau qui contient les étiquettes. L'étiquette d'un sommet x est l'indice du sommet y précédent de x dans le chemin optimum de la racine vers le sommet x.
  • pathMinWeights est le tableau du coût (poids) des chemins depuis la racine jusqu'aux différents sommets.
    pathMinWeights[i] est le poids du chemin entre la racine et le sommet X[i].
  • Alternatives :
    Version 1 :
    • pathTempWeights est le tableau qui contient les poids temporaires des chemins de la racine vers tout sommet. Nous devons ensuite vérifier pour chaque indice si le poids est inférieur au poids au même indice dans pathMinWeights.
    Version 2 :
    • pathTempWeight évite de calculer deux fois le poids du chemin.
    • modified est true si une amélioration est détectée et remet en cause les résultats (un nouveau passage dans la boucle est nécessaire).

Nous utiliserons aussi certaines variables supplémentaires :

  • X est l'ensemble des sommets du graphe
  • n est le nombre de sommets du graphe (la cardinalité de X).

arrayFirstIndex : indice du premier élément dans un tableau5.

Phase d'initialisation

  • k := arrayFirstIndex // Le compteur pointe sur le premier élément d'un tableau.
  • i := indice_de_la_racine // indice (dans X) du sommet racine (départ du chemin).
  • Poids (r->x) :
    • pathMinWeights[i] := 0 // Le chemin de la racine vers la racine a un poids égal à zéro.
    • (j ≠ i) pathMinWeights[j] := maxCost // Valeur hors des limites du possible3.
  • Étiquettes :
    • (i > k) verticesLabels[i] := arrayFirstIndex-1 // Initialisation du tableau avec une valeur hors des limites du tableau6, même pour la racine car elle n'a pas de précédent.

Phase d'exécution


Code (Pseudo-code de Ford-Bellman version 1) (59 lignes) :
  1. //Nombre maximum, sinon ∃ un circuit absorbant
  2.  
  3.   //pour tout sommet excepté la racine
  4.   pour_tout X\{r} faire
  5.  
  6.     /*j est l'indice de y
  7.     ∃ y lié à x par un arc
  8.     et le coût de y est ≤ au coût de tous les arcs*/
  9.     si y : (y,x)  A pathMinWeights[j] ≤ maxCost alors
  10.  
  11.       /*le poids temporaire de x est le minimum des poids
  12.       des chemins pour atteindre x en passant par chaque y*/
  13.       pathTempWeights[i] := minimum{(pathMinWeights[j]+weight(i,j))j};
  14.  
  15.       //poids plus court, amélioration
  16.       si pathTempWeights[i] < pathMinWeights[i] alors
  17.  
  18.         //adaptation de l'étiquette
  19.         verticesLabels[i] := j;
  20.  
  21.       fin si
  22.  
  23.     fin si
  24.  
  25.  
  26.   //si aucune amélioration n'a été détectée
  27.   si j : pathTempWeights[j]=pathMinWeights[j] alors
  28.  
  29.     //arrêt du programme
  30.     afficher("fin de la recherche");
  31.  
  32.  
  33.     //si il reste des sommets à traiter
  34.     si<n alors
  35.  
  36.       //on diminue le nombre de passages restant
  37.       k := k+1;
  38.  
  39.       /*des amélioration ont été détectées
  40.       on met à jour le tableau des coûts*/
  41.       pour_tout X\{r} faire
  42.  
  43.         pathMinWeights[i] := pathTempWeights[i];
  44.  
  45.       fin pour_tout
  46.  
  47.     sinon
  48.  
  49.       //arrêt du programme
  50.       afficher("Détection de circuit absorbant");
  51.       fin_programme;
  52.  
  53.  

Remarques

A la ligne 2, le test de comparaison k < n s'applique aux langages pour lesquels le premier indice d'un tableau est 0. Dans le cas où le premier indice est 1, nous devons remplacer le test par k ≤ n.

La condition ∧ pathMinWeights[j] ≤ maxCost n'est pas strictement nécessaire (car les mises à jour ne se font que lorsqu'une optimisation est détectée), mais elle permet d'éviter de prendre en compte inutilement certaines valeurs lors de la recherche de minimum.

Le pseudo code si ∃ y : (y,x) ∈ A ∧ pathMinWeights[j] ≤ maxCost alors correspond en réalité à un pour_tout car nous devons itérer tous les arcs candidats.

Pseudo codes alternatifs


Code (Pseudo-code de Ford-Bellman version 2) (49 lignes) :
  1. //Nombre maximum, sinon ∃ un circuit absorbant
  2.  
  3.   //si modified=true, cela signifie qu'une optimisation a été détectée
  4.   modified := false;
  5.  
  6.   //pour tout sommet excepté la racine
  7.   pour_tout X\{r} faire
  8.  
  9.     //j est l'indice de y, précédent de x
  10.     pour_tout y : (y,x)  A alors
  11.  
  12.       /*le poids pour atteindre x en passant par ce sommet y*/
  13.       pathTempWeight := pathMinWeights[j]+weight(i,j);
  14.  
  15.       //poids plus court, amélioration
  16.       si pathTempWeight < pathMinWeights[i] alors
  17.  
  18.         //mise à jour de la meilleur valeur
  19.         pathMinWeights[i] := pathTempWeight;
  20.  
  21.         modified := true;//une amélioration est détectée
  22.  
  23.         //adaptation de l'étiquette
  24.         verticesLabels[i] := j;
  25.  
  26.       fin si
  27.  
  28.   //Au moins une améliorationa été détectée
  29.   si modified = true alors
  30.  
  31.     //on diminue le nombre de passages restant
  32.     k := k+1;
  33.  
  34.   //Aucune amélioration n'a été détectée
  35.  
  36.     //arrêt du programme
  37.     afficher("fin de la recherche");
  38.  
  39.  
  40. /*Si un chemin avait été trouvé, le programme se
  41. serait arêté avant ce point*/
  42. afficher("Détection de circuit absorbant");

Dans cette version, nous ne vérifions plus la valeur de k en cours d'itération. Si aucune amélioration n'est plus possible avant de sortir de la boucle principale, l'algorithme s'arrête de lui même.

Si nous arrivons au terme de la boucle principale sans quitter, c'est que nous sommes en présence d'un circuit absorbant.

Dans la version de base, nous devons parcourir tout le tableau des poids si ∀j : pathTempWeights[j]=pathMinWeights[j] alors, alors que nous sommes déjà dans une boucle, ce qui est très coûteux.

Une variable modified nous permet de détecter si les poids ont été mis à jour. Nous ne devons plus utiliser un tableau pathTempWeights, ni itérer ce dernier pour mettre à jour le tableau des poids. La variable modified sert donc de condition de sortie de l'algorithme, au méme titre que la boucle bornée de départ.

Pourquoi utiliser l'algorithme de Ford-Bellman

Lorsque nous ne connaissons pas précisément la destination, et que nous sommes en présence de circuits et de pondérations quelconques, nous operons pour l'algorithme de Ford-Bellman, car des circuits avec pondérations négatives risquent de former des circuits absorbants.

Si nous sommes en possession de plus d'informations, nous nous dirigerons vers un algorithme de type heuristique A*, qui limitera l'exploration à une direction qui correspond à la destination.

Exemples d'application de l'algorithme de Ford-Bellman

Une variante de Ford-Bellman est utilisée dans les protocoles de routage à vecteur-distance, comme par exemple RIP (Routing Information Protocol).

Contents Haut

English translation

You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.

If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.

Thank you in advance.

Document created the 29/12/2009, last modified the 26/10/2018
Source of the printed document:https://www.gaudry.be/en/graphes-ford-bellman.html

The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.

Notes

  1.  pondération : La pondération est une valeur associée à un arc (ou une arête), et correspond au coût du passage par cet arc. Par exemple, il peut s'agir d'une distance entre deux villes représentées chacune par un sommet du graphe.

  2.  retour en arrière : Les résultats stockés dans l'ensemble D sont acquis au fur et à mesure, et ne sont plus mis en doute par la suite.

  3. a,b maxCost : La majorité des pseudo codes utilisent le symbole ∞ (infini) pour représenter une valeur hors des limites du possible, et dont les variations sont insignifiantes. JP Leclercq nous propose donc de travailler avec une valeur qui correspond à la somme des poids des arcs du graphe, car l'infini est une notion qui existe en mathématiques, mais qui ne correspond pas toujours à la réalité de la programmation. Nous utiliserons la notation maxCost, ou même 2maxCost dans les algorithmes pour lesquels cette valeur n'est pas suffisante.

  4.  Incidence : Les arcs incidents à x vers l'intérieur sont les arcs qui ont pour destination le sommet x.

  5.  arrayFirstIndex : Ce n'est pas à proprement parler une variable, mais cela me permet d'éviter d'écrire 0 ou 1 dans le pseudo-code de l'algorithme selon le type de langage utilisé.
    Selon l'implémentation choisie, la collection utilisée peut démarrer son indexation à 0 (ex : tableau en Java) ou à 1 (ex : tableau en Pascal). Par exemple, en Java nous initialisons avec ∀i : previousVertices[i] = 0

  6.  arrayFirstIndex-1 : Comme nous sélectionnons une valeur qui précède le premier indice du tableau, cela signifie que la valeur n'est pas encore significative.

Contents Haut

References

  1. book Language of the document:fr INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (September 2008)
  2. View the nbsp;document Language of the document:uk Bellman–Ford algorithm : Wikipedia (version 28/12/09)
  3. View the nbsp;document Language of the document:fr Cours sur les graphes : les algorithmes : F. Madelaine, C. Simon, L'algorithme de Bellman-Ford et ses variantes (28/12/09)
  4. View the nbsp;document Language of the document:uk Graph Theory Applet : Rensselaer Polytechnic Institute, Démonstration interactive par applet Java (version 28/12/09)

These references and links indicate documents consulted during the writing of this page, or which may provide additional information, but the authors of these sources can not be held responsible for the content of this page.
The author This site is solely responsible for the way in which the various concepts, and the freedoms that are taken with the reference works, are presented here. Remember that you must cross multiple source information to reduce the risk of errors.

Contents Haut