Cette vidéo suppose que vous avez déjà fait un effort de lecture du polycopié et notamment des notions de graphes orientés, plus courts chemins, circuits absorbants.

Il s'agit uniquement d'un exemple d'application de l'algorithme. Quelques commentaires sur cette vidéo:
Par souci de simplicité, nous n'avons pas inclus l'enregistrement des prédécesseurs (matrice 𝜋 du poly) qui permet de reconstruire une solution optimale. Au moment où 𝜙[𝑖,𝑣] est mis à jour, on peut garder la mémoire que sur le nouveau plus court chemin, le prédécesseur de 𝑣 est 𝑢 et enregistrer: 𝜋[𝑖,𝑣]=𝑢
Dans le graphe utilisé comme exemple, le sommet source 𝑠 n'a pas de prédécesseurs. Il pourrait en avoir et si il existe un circuit absorbant passant par 𝑠 alors la valeur de 𝜙[𝑖,𝑠] pourrait devenir négative. L'algorithme reste bien correct. Comme 𝑠 n'a pas de prédécesseurs sur cet exemple, la valeur 𝜙[𝑖,𝑠] va rester à 0 tout du long.
L'ensemble des prédécesseurs est parfois noté Γ−1(𝑢) ou Γ−(𝑢). Nous avons retenu Γ−(𝑢) dans cette vidéo.

Une autres vidéo courtes sur Bellman-Ford:
Comprendre l'optimalité de l'algorithme:
   • 2- Algorithme de Bellman-Ford: Idées ...  

Contact: Nicolas Catusse et Hadrien Cambazard