Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
106
le che min 1 A, B, D, C, E 2 5 8 qui est plus court que 1 A, B, E 2 5 9. On uti lise ainsi
le prin cipe d’optimalité de la pro gram ma tion dyna mique.
Le mathéma ti cien Ford a donné, parmi les nom breux algo rithmes qui peuvent
être employés pour faire ce cal cul d’une manière sys té ma tique, un algo rithme très
simple pour la recherche d’un che min de valeur mini male et qui consiste à :
1) numé ro ter les som mets du graphe dans un ordre quel conque, en obser vant
tou te fois que le som met de départ doit être mar qué X 0 et celui d’arri vée X n21 , si
n est le nombre total de som mets du graphe ;
2) affec ter pro vi soi re ment à tout som met X i (i 2 0) une valeur ou « marque » :
l i 5 1` et poser : l 0 5 0 ; en cours d’exé cu tion de l’algorithme, l i est la valeur
du meilleur che min déjà ren contré, de X 0 à X i ;
3) pour tout som met X j , tel que l j 2 l i . v1 X i , X j 2 , où v(X i , X j ) repré sente la
valuation de l’arc (X i , X j ), rem pla cer l j par l i 1 v1 X i , X j 2 ;
4) reprendre l’étape 3) jus qu’à ce qu’aucun l i ne puisse être modi fié : alors FIN.
On montrera plus bas, qu’en fin d’application de l’algorithme, les l i sont
optimaux.
En fait, l’algo rithme de Ford en résolvant le cas 1 résout aussi le cas 2 : celui de la
recherche des che mins opti maux de X 0 vers tous les autres som mets (qui évidemment
englobe le cas 1 : de X 0 seule ment vers X n-1 ).
Les figures 4.6, 4.7 et 4.8 illus trent le dérou le ment de l’algo rithme de Ford, le som met
A étant celui à par tir duquel les che mins de valeur mini male (qu’on appel lera plus bas,
par abus de lan gage, plus courts che mins) seront cal cu lés. Les valeurs l i sont indi quées
à côté de cha cun des som mets. Dans la figure 4.6 sont cal cu lées les valeurs l i après les
étapes consis
tant à consi dé rer les modi fi
ca tions dues aux arcs
1
(A, E), (E, D), (D, C), (D,
B), (A, B), (C, F) suc ces si ve ment. À cette étape, l’arc (B, C) véri fie : l C 2 l B . 23, une
meilleure valeur l C 5 l B 1 v (B, C) 5 1 est donc déter mi née. Dans la figure 4.7 sont
repor tées les valeurs l i à l’issue de l’étape sui vante : en gras sont repré sen tés les arcs per -
met tant d’effec tuer de nou velles modi fi ca tions aux valeurs l i . Enfin l’arc (F, D) (cf Fig
4.8) entraîne : l D :5 l F 1 v(F, D) 5 21 1 1 5 0. À ce stade, pour tout arc (X i , X j )
on a : l j < l i 1 v(X i , X j ) : c’est le cri tère d’arrêt. La situa tion à la fin de l’exé cu tion de
l’algo rithme de Ford est repré sen tée à la figure 4.8. Les valeurs l i sont alors les lon gueurs
des plus courts che mins issus du som met A. Les arcs repré sen tés en traits épais sont ceux
uti
li sés lors de la der nière modi fi ca tion de la valeur l i asso ciée à cha cun des som mets.
Il est à noter qu’ils forment une arbo res cence de racine A appe lée arbo res cence des plus
courts che mins. Pour tout som met i du graphe, le che min de la racine à ce som met i dans
cette arbo res cence est un plus court che min dans le graphe ; pour tout arc (x i , x j ) de l’arbo -
res cence on a : l j 5 l i 1 v(X i , X j ).
Le lec
teur véri fiera aisé
ment sur l’exemple donné par la figure 4.9, graphe com
por tant un cir cuit absor bant de valeur 22, que l’algo rithme de Ford ne se ter mine
pas. Un cyclage appa raît et les valeurs l B , l C , l D peuvent être ren dues arbi trai re -
ment petites, donc jus qu’à la valeur 2`.
1. Ford n’a pas préconisé un ordre pour le balayage des arcs.
106
le che min 1 A, B, D, C, E 2 5 8 qui est plus court que 1 A, B, E 2 5 9. On uti lise ainsi
le prin cipe d’optimalité de la pro gram ma tion dyna mique.
Le mathéma ti cien Ford a donné, parmi les nom breux algo rithmes qui peuvent
être employés pour faire ce cal cul d’une manière sys té ma tique, un algo rithme très
simple pour la recherche d’un che min de valeur mini male et qui consiste à :
1) numé ro ter les som mets du graphe dans un ordre quel conque, en obser vant
tou te fois que le som met de départ doit être mar qué X 0 et celui d’arri vée X n21 , si
n est le nombre total de som mets du graphe ;
2) affec ter pro vi soi re ment à tout som met X i (i 2 0) une valeur ou « marque » :
l i 5 1` et poser : l 0 5 0 ; en cours d’exé cu tion de l’algorithme, l i est la valeur
du meilleur che min déjà ren contré, de X 0 à X i ;
3) pour tout som met X j , tel que l j 2 l i . v1 X i , X j 2 , où v(X i , X j ) repré sente la
valuation de l’arc (X i , X j ), rem pla cer l j par l i 1 v1 X i , X j 2 ;
4) reprendre l’étape 3) jus qu’à ce qu’aucun l i ne puisse être modi fié : alors FIN.
On montrera plus bas, qu’en fin d’application de l’algorithme, les l i sont
optimaux.
En fait, l’algo rithme de Ford en résolvant le cas 1 résout aussi le cas 2 : celui de la
recherche des che mins opti maux de X 0 vers tous les autres som mets (qui évidemment
englobe le cas 1 : de X 0 seule ment vers X n-1 ).
Les figures 4.6, 4.7 et 4.8 illus trent le dérou le ment de l’algo rithme de Ford, le som met
A étant celui à par tir duquel les che mins de valeur mini male (qu’on appel lera plus bas,
par abus de lan gage, plus courts che mins) seront cal cu lés. Les valeurs l i sont indi quées
à côté de cha cun des som mets. Dans la figure 4.6 sont cal cu lées les valeurs l i après les
étapes consis
tant à consi dé rer les modi fi
ca tions dues aux arcs
1
(A, E), (E, D), (D, C), (D,
B), (A, B), (C, F) suc ces si ve ment. À cette étape, l’arc (B, C) véri fie : l C 2 l B . 23, une
meilleure valeur l C 5 l B 1 v (B, C) 5 1 est donc déter mi née. Dans la figure 4.7 sont
repor tées les valeurs l i à l’issue de l’étape sui vante : en gras sont repré sen tés les arcs per -
met tant d’effec tuer de nou velles modi fi ca tions aux valeurs l i . Enfin l’arc (F, D) (cf Fig
4.8) entraîne : l D :5 l F 1 v(F, D) 5 21 1 1 5 0. À ce stade, pour tout arc (X i , X j )
on a : l j < l i 1 v(X i , X j ) : c’est le cri tère d’arrêt. La situa tion à la fin de l’exé cu tion de
l’algo rithme de Ford est repré sen tée à la figure 4.8. Les valeurs l i sont alors les lon gueurs
des plus courts che mins issus du som met A. Les arcs repré sen tés en traits épais sont ceux
uti
li sés lors de la der nière modi fi ca tion de la valeur l i asso ciée à cha cun des som mets.
Il est à noter qu’ils forment une arbo res cence de racine A appe lée arbo res cence des plus
courts che mins. Pour tout som met i du graphe, le che min de la racine à ce som met i dans
cette arbo res cence est un plus court che min dans le graphe ; pour tout arc (x i , x j ) de l’arbo -
res cence on a : l j 5 l i 1 v(X i , X j ).
Le lec
teur véri fiera aisé
ment sur l’exemple donné par la figure 4.9, graphe com
por tant un cir cuit absor bant de valeur 22, que l’algo rithme de Ford ne se ter mine
pas. Un cyclage appa raît et les valeurs l B , l C , l D peuvent être ren dues arbi trai re -
ment petites, donc jus qu’à la valeur 2`.
1. Ford n’a pas préconisé un ordre pour le balayage des arcs.