Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
114
Il est facile de trans for mer cer tains algo rithmes valables pour le pre mier cas
en algo rithmes uti li sables pour le second, tel l’algo rithme de Ford. Les cir -
cuits absor bants sont alors de valeur stric te ment posi tive et les tests de type :
« l i 1 v1 i, j2 , l j » sont rem pla cés par : « l i 1 v1 i, j2 . l j ». (Atten tion :
l’algo rithme de Dijkstra ne s’adapte pas au cas d’une maxi mi sa tion.)
Figure 4.12 Une exé cu tion de l’algo rithme de Bellman
4.3 pro blèmes d ’ ordon nAn ce ment
en ges tion de pro jets
Il s’agit d’une appli ca tion directe des méthodes de recherche des che mins opti maux
dans un graphe. Nous ver rons, plus pré ci sé ment, que pour résoudre les pro blèmes
d’ordon nan ce ment ci- dessous, l’on déter mine des che mins de valeur maximale.
On dit que l’on a affaire à un pro blème d’ordon nan ce ment lorsque, en vue de la
réa li sa tion d’un objec tif quel conque, il faut accom plir un ensemble de tâches (ou
114
Il est facile de trans for mer cer tains algo rithmes valables pour le pre mier cas
en algo rithmes uti li sables pour le second, tel l’algo rithme de Ford. Les cir -
cuits absor bants sont alors de valeur stric te ment posi tive et les tests de type :
« l i 1 v1 i, j2 , l j » sont rem pla cés par : « l i 1 v1 i, j2 . l j ». (Atten tion :
l’algo rithme de Dijkstra ne s’adapte pas au cas d’une maxi mi sa tion.)
Figure 4.12 Une exé cu tion de l’algo rithme de Bellman
4.3 pro blèmes d ’ ordon nAn ce ment
en ges tion de pro jets
Il s’agit d’une appli ca tion directe des méthodes de recherche des che mins opti maux
dans un graphe. Nous ver rons, plus pré ci sé ment, que pour résoudre les pro blèmes
d’ordon nan ce ment ci- dessous, l’on déter mine des che mins de valeur maximale.
On dit que l’on a affaire à un pro blème d’ordon nan ce ment lorsque, en vue de la
réa li sa tion d’un objec tif quel conque, il faut accom plir un ensemble de tâches (ou