Problèmes de chemins
129
chemin de valeur minimale). Il suffit en effet d'affecter à chaque sommet un poids
égal à 0 et de recalculer les
Si
Algorithme 3 : Algorithme de Bellmann-Kalaba
Cet algorithme va nous donner l'occasion d'utiliser le principe d'optimalité de Bellmann,
qui est à la base d'une technique d'optimisation appelée « programmation dynamique »,
et dont la simplicité n'empêche pas la fécondité.
Dans le cas qui nous intéresse, c'est-à-dire la détermination du chemin de valeur
minimale entre
. Le principe d'optimalité s'énonce de la façon suivante : soit
le chemin de valeur minimale entre
; alors, pour tout
le chemin
est le chemin de valeur minimale entre
Plus synthétiquement : tout sous-chemin d'un chemin optimal est optimal.
Ce principe est parfaitement évident : si en effet il existait un chemin
meilleur
que
alors le chemin
serait
meilleur
que
, qui a été pourtant supposé optimal.
Plus précisément, dans l'algorithme de Bellmann-Kalaba, on utilise ce principe de la
façon suivante :
soit un sommet du graphe, et considérons l'ensemble
des suivants de (j
.
Prenons maintenant le chemin de valeur minimale entre
de longueur inférieure ou
égale à p. Soit
ce chemin ;
. Il est évident que le chemin
est le chemin reliant
de longueur inférieure ou égale à
et de
valeur minimale.
Pratiquement on opère ainsi : on appelle
la valeur de l'arc reliant
, si cet arc
n'existe pas,
. On appelle
la valeur du chemin de valeur minimale de
longueur inférieure ou égale à reliant
À la première étape on a :
puis on calcule pour
par la formule :
en posant pour tout
Comme le chemin de valeur minimale entre un sommet quelconque et a une longueur
inférieure ou égale à
, on arrête les calculs lorsque
i
p
i
p
i
1)
(
)
(
=