Le calcul d'un plus court chemin procède par améliorations successives. À chaque étape, on examine une arête et on se demande si elle raccourcit le trajet connu vers son extrémité.
L'état actuel
| Sommet | Distance connue depuis le départ |
|---|---|
| A | 0 |
| B | 7 |
| C | 3 |
| D | 9 |
Les arêtes examinées
| De | Vers | Poids |
|---|---|---|
| C | B | 2 |
| C | D | 1 |
La règle
Passer par u pour atteindre v coûte distance(u) + poids. Si ce total est strictement inférieur à la distance connue de v, elle est remplacée. Sinon, rien ne change.
Objectif
Donner les trois distances demandées.