appliction de l'algorithme sur le graphe precedent :
S = {X0}
Xp=X0 : (0,1) ∏(X1)> ∏(X0)+3 => ∏(X1) = 3
(0,4) ∏(X4)> ∏(X0)+2 => ∏(X1) = 2
Xp=X4 : S={X0,X4}
(4,3) ∏(X3)> ∏(X4)+1 => ∏(X3) = 3
Xp=X1 : S={X0,X4,X1}
(1,2) ∏(X2)> ∏(X1)+2 => ∏(X2) = 5
(1,5) ∏(X5)> ∏(X1)+2 => ∏(X5) = 5
Xp=X3 : S={X0,X4,X1,X3}
(3,2) ∏(X2)> ∏(X3)+2 => faux
(3,5) ∏(X5)> ∏(X3)+3 => faux
(3,6) ∏(X6)> ∏(X3)+6 => ∏(X6) = 9
Xp=X2 : S={X0,X4,X1,X3,X2}
(2,5) ∏(X5)> ∏(X2)+1 => faux
Xp=X5 : S={X0,X4,X1,X3,X2,X5}
(5,6) ∏(X6)> ∏(X5)+2 => ∏(X6) = 7
Xp=X5 : => S=X
Arret.
Le plus court chemin de X0 a X6 :
X0,X1,X5,X6 de longeur 7.