4.2 Appli ca tions aux che mins opti maux
109
© Dunod – Toute reproduction non autorisée est un délit.
concer nant les aspects de com plexité de cet algo rithme en consul tant les nom breux
ouvrages trai tant d’algo rith mique dans les graphes, en par ti cu lier la réfé rence [8].
Rappelons enfin que l’algo rithme de Ford peutêtre trans posé à la recherche
de che mins de valeur maximale. Dans ce cas, un cir cuit est absor bant si sa
valeur est strictement positive. Il suffit de modifier l’initialisation comme suit :
l i 5 2 ` (i 2 0) et l 0 5 0 ; puis au 3), remplacer « > » par « < ».
Méthode matricielle
Voici main te nant un algo rithme qui per met d’obte nir les che mins de valeur mini male
entre toute paire de som mets du graphe : c’est le cas 3. Il est dû notam ment à G.
Demoucron et a été publié indé pen dam ment aux États- Unis par R. W. Floyd.
Après avoir numé roté les som mets de 1 à n (et non de 0 à n 2 1 comme cidessus), poser :
vr ij 5 b
v(X i , X j ) si (X i , X j ) H U
1`
si (X i , X j ) x U,
et mettre ces valeurs dans une matrice n 3 n, notée D 0 .
À chaque étape, k > 1, de l’algo rithme, cal cu ler :
vr
1k212
ij
5 v
1k212
ik
1 v
1k212
kj
,
puis :
v
1k2
ij 5 min b vr
1k212
ij
; v
1k212
ij
r ,
d’où : D k 5 min b Dr k21 , D k21 r , où D k 5 cv
(k)
ij d , matrice n 3 n.
Arrê ter dès que : D k 5 D k21 .
Si le graphe com porte un cir cuit absor bant, alors à une cer taine étape p, on aura
v
1p2
ii , 0 : il convient alors d’arrê ter.
Appli quons cet algo rithme à l’exemple ci- dessous :
On a suc ces si ve ment (en notant 1` par un tiret) :
109
© Dunod – Toute reproduction non autorisée est un délit.
concer nant les aspects de com plexité de cet algo rithme en consul tant les nom breux
ouvrages trai tant d’algo rith mique dans les graphes, en par ti cu lier la réfé rence [8].
Rappelons enfin que l’algo rithme de Ford peutêtre trans posé à la recherche
de che mins de valeur maximale. Dans ce cas, un cir cuit est absor bant si sa
valeur est strictement positive. Il suffit de modifier l’initialisation comme suit :
l i 5 2 ` (i 2 0) et l 0 5 0 ; puis au 3), remplacer « > » par « < ».
Méthode matricielle
Voici main te nant un algo rithme qui per met d’obte nir les che mins de valeur mini male
entre toute paire de som mets du graphe : c’est le cas 3. Il est dû notam ment à G.
Demoucron et a été publié indé pen dam ment aux États- Unis par R. W. Floyd.
Après avoir numé roté les som mets de 1 à n (et non de 0 à n 2 1 comme cidessus), poser :
vr ij 5 b
v(X i , X j ) si (X i , X j ) H U
1`
si (X i , X j ) x U,
et mettre ces valeurs dans une matrice n 3 n, notée D 0 .
À chaque étape, k > 1, de l’algo rithme, cal cu ler :
vr
1k212
ij
5 v
1k212
ik
1 v
1k212
kj
,
puis :
v
1k2
ij 5 min b vr
1k212
ij
; v
1k212
ij
r ,
d’où : D k 5 min b Dr k21 , D k21 r , où D k 5 cv
(k)
ij d , matrice n 3 n.
Arrê ter dès que : D k 5 D k21 .
Si le graphe com porte un cir cuit absor bant, alors à une cer taine étape p, on aura
v
1p2
ii , 0 : il convient alors d’arrê ter.
Appli quons cet algo rithme à l’exemple ci- dessous :
On a suc ces si ve ment (en notant 1` par un tiret) :