4.2 Appli ca tions aux che mins opti maux
111
© Dunod – Toute reproduction non autorisée est un délit.
Ici l’arborescence des plus courts chemins se résume au seul chemin :
(X 1 , X 2 , X 4 , X 3 , X 5 , X 6 ).
La procédure de la figure 4.10, très simple, résume l’algo
rithme :
pour k 5 1 à n faire
pour i 5 1 à n faire
pour j 5 1 à n faire
v ij d min 3 1 v ik 1 v kj 2 , v ij 4.
Figure 4.10
Tel quel, l’algo rithme n’exige qu’un seul balayage de la matrice.
L’avan tage de cet algo rithme est de don ner le che min de valeur mini male entre
tout couple de som mets, c’est le “cas 3”. L’algo
rithme est évi dem ment fini ; de plus, il
pro cède par exten sion opti male de sous- chemins mini maux ; il atteint donc le che min
de valeur mini male (ce qui résulte de la programmation dynamique).
Le lec teur remar quera l’ana lo gie entre cet algo rithme et celui de Roy- Warshall
(pour déter mi ner la fer me ture tran si tive d’un graphe) donné au cha pitre 2.
4.2.2 Cas des valuations posi tives : algo rithme de Dijkstra
L’ordre dans lequel les arcs sont exa mi nés dans l’algo rithme de Ford cal cu lant les
plus courts che mins issus d’un som met donné s, est arbi traire. Il s’en suit que, pour
cer tains exemples, le nombre d’ité ra tions effec tuées au cours de l’algo rithme peut
être très élevé. Dans le cas où les valuations des arcs sont posi tives
1
, nous allons
don ner un algo rithme dû à Dijkstra qui évite cet inconvé nient. Ce der nier reprend
le même prin cipe que l’algo rithme de Ford, en ajou tant une règle éta blis sant l’ordre
dans lequel les arcs du graphe sont exa mi nés. On part du som met s pour abou tir au
sommet t : c’est le cas 1 (mais, en fait, on va résoudre le cas 2 qui englobe le cas 1).
Dans cet algo rithme, le trai te ment d’un som met i consis tera à exa mi ner suc ces si -
ve ment tous les arcs d’ori gine i. Tous les som mets du graphe seront trai tés une fois et
une seule, sui vant un ordre déter miné dyna mi que ment au cours de l’algo rithme.
1. ini tia le ment l i d 1 `, pour i 2 s ; l s d 0 ; tout som met est « non traité » ;
2. tant que tout les som mets ne sont pas trai tés faire
3.
soit i un som met non traité, de valeur l i mini male (parmi les som mets
non trai tés)
4.
pour tout arc (i, j) faire
5.
si l i 1 v1 i, j2 , l j alors l j d l i 1 v1 i, j2
6. le som met i est « traité »
La figure 4.11 illustre sur un exemple le dérou
le ment de l’algo rithme. Le graphe
traité est repré senté en haut à gauche après la phase d’ini tia li sation. Les plus courts
che mins à déter mi ner ont pour ori gine le som met A. Les som mets trai tés sont gri sés
1. Ce qui entraîne l’absence de cir cuit absor bant (de valeur , 0) dans une minimisation.
111
© Dunod – Toute reproduction non autorisée est un délit.
Ici l’arborescence des plus courts chemins se résume au seul chemin :
(X 1 , X 2 , X 4 , X 3 , X 5 , X 6 ).
La procédure de la figure 4.10, très simple, résume l’algo
rithme :
pour k 5 1 à n faire
pour i 5 1 à n faire
pour j 5 1 à n faire
v ij d min 3 1 v ik 1 v kj 2 , v ij 4.
Figure 4.10
Tel quel, l’algo rithme n’exige qu’un seul balayage de la matrice.
L’avan tage de cet algo rithme est de don ner le che min de valeur mini male entre
tout couple de som mets, c’est le “cas 3”. L’algo
rithme est évi dem ment fini ; de plus, il
pro cède par exten sion opti male de sous- chemins mini maux ; il atteint donc le che min
de valeur mini male (ce qui résulte de la programmation dynamique).
Le lec teur remar quera l’ana lo gie entre cet algo rithme et celui de Roy- Warshall
(pour déter mi ner la fer me ture tran si tive d’un graphe) donné au cha pitre 2.
4.2.2 Cas des valuations posi tives : algo rithme de Dijkstra
L’ordre dans lequel les arcs sont exa mi nés dans l’algo rithme de Ford cal cu lant les
plus courts che mins issus d’un som met donné s, est arbi traire. Il s’en suit que, pour
cer tains exemples, le nombre d’ité ra tions effec tuées au cours de l’algo rithme peut
être très élevé. Dans le cas où les valuations des arcs sont posi tives
1
, nous allons
don ner un algo rithme dû à Dijkstra qui évite cet inconvé nient. Ce der nier reprend
le même prin cipe que l’algo rithme de Ford, en ajou tant une règle éta blis sant l’ordre
dans lequel les arcs du graphe sont exa mi nés. On part du som met s pour abou tir au
sommet t : c’est le cas 1 (mais, en fait, on va résoudre le cas 2 qui englobe le cas 1).
Dans cet algo rithme, le trai te ment d’un som met i consis tera à exa mi ner suc ces si -
ve ment tous les arcs d’ori gine i. Tous les som mets du graphe seront trai tés une fois et
une seule, sui vant un ordre déter miné dyna mi que ment au cours de l’algo rithme.
1. ini tia le ment l i d 1 `, pour i 2 s ; l s d 0 ; tout som met est « non traité » ;
2. tant que tout les som mets ne sont pas trai tés faire
3.
soit i un som met non traité, de valeur l i mini male (parmi les som mets
non trai tés)
4.
pour tout arc (i, j) faire
5.
si l i 1 v1 i, j2 , l j alors l j d l i 1 v1 i, j2
6. le som met i est « traité »
La figure 4.11 illustre sur un exemple le dérou
le ment de l’algo rithme. Le graphe
traité est repré senté en haut à gauche après la phase d’ini tia li sation. Les plus courts
che mins à déter mi ner ont pour ori gine le som met A. Les som mets trai tés sont gri sés
1. Ce qui entraîne l’absence de cir cuit absor bant (de valeur , 0) dans une minimisation.