Vidéo (7 min): Application de Bellman-Ford sur un exemple


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 \pi du poly) qui permet de reconstruire une solution optimale. Au moment où \phi[i,v] est mis à jour, on peut garder la mémoire que sur le nouveau plus court chemin, le prédécesseur de v est u et enregistrer:

\pi[i,v] = u

  • Dans le graphe utilisé comme exemple, le sommet source s n'a pas de prédécesseurs. Il pourrait en avoir et si il existe un circuit absorbant passant par s alors la valeur de \phi[i,s] pourrait devenir négative. L'algorithme reste bien correct. Comme s n'a pas de prédécesseurs sur cet exemple, la valeur \phi[i,s] va rester à 0 tout du long.

  • L'ensemble des prédécesseurs est parfois noté \Gamma^{-1}(u) ou \Gamma^{-}(u). Nous avons retenu \Gamma^{-}(u) dans cette vidéo.

Contact: Nicolas Catusse et Hadrien Cambazard

Last modified: Thursday, 12 September 2019, 9:47 AM