4.2 Appli ca tions aux che mins opti maux
107
© Dunod – Toute reproduction non autorisée est un délit.
Figure 4.6 l C 2 l B . 23 1 l C :5 l B 2 3 5 1 : cf ci dessous.
Figure 4.7 La situa tion après la modi fi ca tion pré cé dente puis la modi fi ca tion l E entraî née
par l’uti li sation de l’arc (B, E) et celle de l F entraî née par (C, F).
Lors    qu’il n’est plus pos    sible de modi    fier les l i , on a donc trouvé la valeur mini -
male soit l n21 , des che mins entre X 0 et X n21 (pourvu qu’il existe au moins un che -
min entre X 0 et X n21 ). Les l i , pour chaque X i , donnent la valeur mini male des che -
mins entre X 0 et X i : on a alors résolu le cas 2.
Pour retrou ver le che min de valeur mini male lui- même de X 0 à X n21 , il suf    fit de 
déter mi ner, par tant de X n21 , le pré dé ces seur X p1 , tel que l n21 2 l p1 5 v1 X p1 , X n21 2 ,
puis le pré dé ces seur X p2 de X p1 , tel que : l p1 2 l p2 5 v1 X p2 , X p1 2 , etc. et de remon ter
jus qu’à X 0 . Il peut natu rel le ment y avoir plu sieurs che mins de valeur mini male (mais
leur valeur est évidemment unique).