4.2 Appli ca tions aux che mins opti maux
105
© Dunod – Toute reproduction non autorisée est un délit.
Exemple. (che mins de valeur mini male).
Soit un cro quis géo gra phique, repré sen tant les routes qui existent entre deux points
A et F : les valeurs indi quées sur chaque route sont des dis tances kilo mé triques ; de
plus, comme il s’agit d’un pays de mon tagne à routes étroites, la cir cu la tion y a lieu à
sens unique : d’où les flèches por tées sur le des sin (figure 4.4). Il existe évi dem ment
un cer tain nombre de che mins condui sant de A en F, mais on vou drait en trou ver un
de lon gueur mini male, sans les énu mé rer.
Figure 4.4
Figure 4.5
Employons à cet effet un graphe valué, dont les som mets repré sentent les points de
pas sage pos sible et les arcs (flèches) les routes pra ti cables (figure 4.5).
Nous allons exa mi ner, pour chaque point, la lon gueur kilo mé trique (ou « valeur »)
du plus court che min y condui sant à par tir de A.
Pour B, c’est la route AB 5 3 ; pour D, la route 1 A, B, D 2 5 3 1 2 5 5 (et non
l’arc (A, D)) ; pour C, la route 1 A, B, D, C 2 5 3 1 2 1 2 5 7 (et non l’arc (A, C)) ;
pour E la route 1 A, B, D, C, E 2 5 3 1 2 1 2 1 1 5 8 (et non (A, B, E), ou (A, C, E)
ou (A, D, C, E)). Il en résulte que, pour aller de A en F par le plus court che min, il
faut pas ser par B, D, C et E. On a un che min de valeur mini male 10.
Plus géné ra le ment, on s’inté resse au pro blème de déter mi na tion des che mins de
valeur mini male : soit d’un som met donné vers un autre som met (cas 1) comme ici
de A à F, ou bien d’un som met donné vers tous les autres som mets (cas 2) ou encore
entre tout couple de som mets (cas 3).
Algo rithme de Ford
1
(chemins de valeur minimale)
Pour un graphe com por tant de nom breux som mets, une pro cé dure aussi peu assu rée
ris que rait de conduire à de longs cal culs et sans doute à des oublis. Il est d’autre part
évident, par exemple, que lorsque les plus courtes dis tances de A aux points B, C et
D ont été cal cu lées, il est inutile, pour avoir la plus courte dis tance entre A et E, de
remon ter au- delà des prédécesseurs de E, c-à-d des points qui sont direc te ment liés
par un arc (une flèche) à E : en d’autres termes, il suf fit de com pa rer les che mins (A,
B, E) et (A, B, D, C, E), car on sait que le plus court che min entre A et B est AB 5 3
et le plus court che min entre A et C, 1 A, B, D, C 2 5 7. Fina le ment, entre A et E, c’est
1. On rap pelle que le mot algo rithme résulte de la cor rup tion du nom du grand mathéma ti cien
arabe Al Khwarizmi qui vivait au ix
e siècle, et qui signi fie sim ple ment : pro cédé per met tant de
résoudre un pro blème en un nombre fini d’opé ra tions.
105
© Dunod – Toute reproduction non autorisée est un délit.
Exemple. (che mins de valeur mini male).
Soit un cro quis géo gra phique, repré sen tant les routes qui existent entre deux points
A et F : les valeurs indi quées sur chaque route sont des dis tances kilo mé triques ; de
plus, comme il s’agit d’un pays de mon tagne à routes étroites, la cir cu la tion y a lieu à
sens unique : d’où les flèches por tées sur le des sin (figure 4.4). Il existe évi dem ment
un cer tain nombre de che mins condui sant de A en F, mais on vou drait en trou ver un
de lon gueur mini male, sans les énu mé rer.
Figure 4.4
Figure 4.5
Employons à cet effet un graphe valué, dont les som mets repré sentent les points de
pas sage pos sible et les arcs (flèches) les routes pra ti cables (figure 4.5).
Nous allons exa mi ner, pour chaque point, la lon gueur kilo mé trique (ou « valeur »)
du plus court che min y condui sant à par tir de A.
Pour B, c’est la route AB 5 3 ; pour D, la route 1 A, B, D 2 5 3 1 2 5 5 (et non
l’arc (A, D)) ; pour C, la route 1 A, B, D, C 2 5 3 1 2 1 2 5 7 (et non l’arc (A, C)) ;
pour E la route 1 A, B, D, C, E 2 5 3 1 2 1 2 1 1 5 8 (et non (A, B, E), ou (A, C, E)
ou (A, D, C, E)). Il en résulte que, pour aller de A en F par le plus court che min, il
faut pas ser par B, D, C et E. On a un che min de valeur mini male 10.
Plus géné ra le ment, on s’inté resse au pro blème de déter mi na tion des che mins de
valeur mini male : soit d’un som met donné vers un autre som met (cas 1) comme ici
de A à F, ou bien d’un som met donné vers tous les autres som mets (cas 2) ou encore
entre tout couple de som mets (cas 3).
Algo rithme de Ford
1
(chemins de valeur minimale)
Pour un graphe com por tant de nom breux som mets, une pro cé dure aussi peu assu rée
ris que rait de conduire à de longs cal culs et sans doute à des oublis. Il est d’autre part
évident, par exemple, que lorsque les plus courtes dis tances de A aux points B, C et
D ont été cal cu lées, il est inutile, pour avoir la plus courte dis tance entre A et E, de
remon ter au- delà des prédécesseurs de E, c-à-d des points qui sont direc te ment liés
par un arc (une flèche) à E : en d’autres termes, il suf fit de com pa rer les che mins (A,
B, E) et (A, B, D, C, E), car on sait que le plus court che min entre A et B est AB 5 3
et le plus court che min entre A et C, 1 A, B, D, C 2 5 7. Fina le ment, entre A et E, c’est
1. On rap pelle que le mot algo rithme résulte de la cor rup tion du nom du grand mathéma ti cien
arabe Al Khwarizmi qui vivait au ix
e siècle, et qui signi fie sim ple ment : pro cédé per met tant de
résoudre un pro blème en un nombre fini d’opé ra tions.