http://membres.multimania.fr/baekoasiswww.baekoasis.i8.comsoit le graphe
1 2 3 4 5
1 0 15 oo oo 4
2 0 0 oo oo oo
3 oo 3 0 2 oo
4 10 3 oo 0 oo
5 oo oo 7 5 0
Remarque : le graphe est orienté, oo : pas d'arc
Initialisations
S = {1} ; T = {2, 3, 4, 5} ; l = (0, 15, ¥, ¥, 4); p = (NIL, 1, NIL, NIL, 1)
1ère itération
i = 5 car l(5) = min(15, ¥, ¥, 4) = 4
S = {1, 5}; T = {2, 3, 4}
les successeurs de 5 dans T sont 3 et 4
l(3) prend la nouvelle valeur min(¥; l(5) + d(5; 3)) = min(¥; 4 + 7) = 11; p(3) = 5
l(4) prend la nouvelle valeur min(¥; l(5) + d(5; 4)) = 9; p(4) = 5
d'où les nouveaux vecteurs l = (0, 15, 11, 9, 4) et p = (NIL, 1, 5, 5, 1)
2ème itération
i = 4; l(4) = 9
S = {1, 5, 4}; T = {2, 3}
le seul successeur de 4 dans T est 2
l(2) prend la nouvelle valeur min(¥; l(4) + d(4; 2)) = min(15; 9 + 3) = 12; p(2) = 4
d'où les nouveaux vecteurs l = (0, 12, 11, 9, 4) et p = (NIL, 4, 5, 5, 1)
3ème itération
i = 3; l(3) = 11
S = {1, 5, 4, 3}; T = {2}
le seul successeur de 3 dans T est 2
l(2) garde sa valeur car min(12; l(3) + d(3; 2)) = min(12; 11 + 3) = 12
d'où les vecteurs inchangés l = (0, 12, 11, 9, 4) et p = (NIL, 4, 5, 5, 1)
4ème itération
i = 2; l(2) = 12
S = {1, 5, 4, 3, 2}; T = {}; FIN
l = (0, 12, 11, 9, 4)
p = (NIL, 4, 5, 5, 1)
Par exemple, le chemin minimal de 1 à 4 est de coût 9.
C'est le chemin 1-5-4, car p(4) = 5 et p(5) = 1.