Problèmes de chemins
119
Démonstration :
Tout d'abord, a été calculé par la formule (1) à partir d'un sommet
. Le fait que
est fini indique qu'il y a un chemin entre
passant par ( Si n'est pas fini, il
n'existe pas de chemin entre les sommets de et ceux de
, et l'algorithme s'arrête).
Pour montrer que ce chemin est le chemin de valeur minimale entre
, prenons un
autre chemin : il se décompose en deux sous-chemins, l'un
jusqu'au premier sommet
de
rencontré, soit et l'autre
entre
. Par construction de
par la formule
(1), on a : valeur de
, et puisque est caractérisé par le minimum des
sur
.
Valeur de µ
Par ailleurs, puisque les valeurs des arcs sont positives ou nulles
Valeur de
au total
Valeur de µ
µ étant quelconque, est la valeur du chemin le plus court entre
D'où l'algorithme :
pour
}
.....
2
{
=
{1}
=
n
S
X
S
i
j
min
=
S
X
i