Problèmes de chemins
125
Soit en sommant :
Ce que l'on a exclu. De là, il résulte que, comme la suite
a tous ses éléments
distincts et comme le nombre de sommets du graphe est fini, on trouve au bout d'un
certain temps le sommet 1. On a alors :
…
Soit en sommant
i
i
s
i
s
i
s
i
i
i
1
1
1
1
.....
=
=



mesure la valeur du chemin
trouvé par cette méthode.
Montrons que ce chemin est bien le chemin le plus court. Soit en effet un autre chemin
Puisqu'on a appliqué l'algorithme, on a obligatoirement
Soit en sommant
i
k
k
i




.....
1
u
u
i

La valeur du chemin est donc supérieure ou égale à la valeur du chemin trouvé par
la procédure ci-dessus.
Remarque : il peut y avoir naturellement plusieurs chemins de valeur minimale.
Pratiquement, on examine les dans l'ordre de numérotation des sommets et en testant
la règle c) sur les arcs issus de chaque sommet. Dans la mesure où la numérotation des
sommets est arbitraire, on peut avoir des arcs
avec
. Alors, une valeur
peut