1- Algorithme de Bellman-Ford: Application 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 𝜋 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:

Contact: Nicolas Catusse et Hadrien Cambazard

[moustaphakachab]

Merci, votre vidéo m'a beaucoup aidé ! J'espère que vous continuerez :)

[alexh]

bonjour, merci pour cette vidéo qui m’a permis de comprendre le fonctionnement de l’algorithme. Il m’a manqué juste un élément : le PCC à la fin, après avoir complété la matrice, avoir l’identification du PCC : est-ce s-b-d ? s-c-e ? etc… cette dernière étape n’est pas claire pour moi.

[Nourakoulate]

Pourquoi il n'y a pas d'exemple avec un graphe non orienté ?

[mohamedibrahimhassan]

ça marche aussi avec un graphe non-orienté ?

[teschan]

J'ai une question
Où cette programmation on va utiliser ?
Et on fait quoi avec cette programmation ?

[aoscugkg]

Svp besoin d'un cours résumé en Recherche opérationnelle