4.2 Appli ca tions aux che mins opti maux
113
© Dunod – Toute reproduction non autorisée est un délit.
En uti li sant des struc tures de don nées approp riées, la com plexité de l’algo rithme de
Dijkstra est O(m log n). Le lec teur pourra consul ter [3] ou [8] pour la démons tra tion
de la vali dité et le cal cul de la com plexité de cet algo rithme. Enfin indiquons que cet
algorithme ne peut pas être adapté à la recherche de chemins de valeur maximale.
4.2.3 Cas des graphes sans cir cuit : algo rithme de Bellman
Nous allons consi dé rer ici le cas le plus simple : celui des graphes sans cir cuit (donc
a fortiori sans circuit absorbant). Nous don nons un algo rithme dû à Bellman cal cu -
lant les plus courts che mins à par tir d’une ori gine s. Repre nant le prin cipe de l’algo -
rithme de Ford, en ajou tant une règle sup plé men taire déter mi nant un ordre d’exa men
des arcs du graphe, cet algo rithme a une com plexité plus faible O(m).
Avant de don ner l’algo rithme de Bellman, nous allons défi nir la notion d’ordre
topologique dans un graphe. Un ordre topologique est une numé ro ta tion des som mets
d’un graphe sans cir cuit satis faisant les contraintes sui vantes : si n(i) est le numéro affecté
à un som met i, n(i) est com pris entre 1 et n ; en outre deux som mets dif fé rents reçoivent
un numéro dif fé rent ; et, pour tout arc (i, j) du graphe, on a : n 1 i 2 , n 1 j2 . Il est aisé de
démon trer qu’un graphe est sans cir cuit si et seule ment si il admet un ordre topologique
(cf. fin du §3.2). D’autre part, des algo rithmes de com plexité O(m) peuvent aisé ment être
mis en œuvre pour déter mi ner une numé ro ta tion topologique ou prouver qu’elle n’existe
pas. Dans la suite de cette par tie, nous confon drons le nom et le numéro attri bué à un
som met dans la numé ro ta tion topologique. De plus nous sup po se rons que les plus courts
che mins à déter mi ner ont pour ori gine le som met 1 et que le sommet n est une sortie.
Comme dans l’algo rithme de Dijkstra, 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 une numé ro ta tion topologique des som mets déterminée
préalablement. L’algo rithme de Bellman s’écrit de la manière sui vante :
1. ini tia le ment l i d 1`, i 2 1 ; l 1 d 0
2. pour i 5 1 à n 2 1 faire
3. pour tout arc (i, j) faire
4.
si l i 1 v1 i, j2 , l j alors l j d l i 1 v1 i, j2
Le lec teur véri fiera ci après qu’on a bien la numé ro ta tion topologique des som -
mets : pour tout arc (i, j), on a : i , j (cf. fig 4.12 0 ).
La figure 4.12 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. Pour chaque
ité ra tion, le som met en cours de trai te ment est cer clé en épais et les arcs modi fiant
les valeurs l i sont repré
sen tés en gras. Sur la figure en bas à droite, les arcs en traits
doubles sont ceux uti li sés lors de la der
nière modi fi ca tion des valeurs l 1 . En remon -
tant ces arcs nous obte nons un plus court che min issu du som met 1.
Remarque. Nous avons traité jus qu’à présent le cas des che mins de valeur
mini male ; nous allons voir que, dans quelques pro blèmes comme ceux
d'ordonnancement, ce sont, au contraire, les che mins de valeur maximale qui
importent.
113
© Dunod – Toute reproduction non autorisée est un délit.
En uti li sant des struc tures de don nées approp riées, la com plexité de l’algo rithme de
Dijkstra est O(m log n). Le lec teur pourra consul ter [3] ou [8] pour la démons tra tion
de la vali dité et le cal cul de la com plexité de cet algo rithme. Enfin indiquons que cet
algorithme ne peut pas être adapté à la recherche de chemins de valeur maximale.
4.2.3 Cas des graphes sans cir cuit : algo rithme de Bellman
Nous allons consi dé rer ici le cas le plus simple : celui des graphes sans cir cuit (donc
a fortiori sans circuit absorbant). Nous don nons un algo rithme dû à Bellman cal cu -
lant les plus courts che mins à par tir d’une ori gine s. Repre nant le prin cipe de l’algo -
rithme de Ford, en ajou tant une règle sup plé men taire déter mi nant un ordre d’exa men
des arcs du graphe, cet algo rithme a une com plexité plus faible O(m).
Avant de don ner l’algo rithme de Bellman, nous allons défi nir la notion d’ordre
topologique dans un graphe. Un ordre topologique est une numé ro ta tion des som mets
d’un graphe sans cir cuit satis faisant les contraintes sui vantes : si n(i) est le numéro affecté
à un som met i, n(i) est com pris entre 1 et n ; en outre deux som mets dif fé rents reçoivent
un numéro dif fé rent ; et, pour tout arc (i, j) du graphe, on a : n 1 i 2 , n 1 j2 . Il est aisé de
démon trer qu’un graphe est sans cir cuit si et seule ment si il admet un ordre topologique
(cf. fin du §3.2). D’autre part, des algo rithmes de com plexité O(m) peuvent aisé ment être
mis en œuvre pour déter mi ner une numé ro ta tion topologique ou prouver qu’elle n’existe
pas. Dans la suite de cette par tie, nous confon drons le nom et le numéro attri bué à un
som met dans la numé ro ta tion topologique. De plus nous sup po se rons que les plus courts
che mins à déter mi ner ont pour ori gine le som met 1 et que le sommet n est une sortie.
Comme dans l’algo rithme de Dijkstra, 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 une numé ro ta tion topologique des som mets déterminée
préalablement. L’algo rithme de Bellman s’écrit de la manière sui vante :
1. ini tia le ment l i d 1`, i 2 1 ; l 1 d 0
2. pour i 5 1 à n 2 1 faire
3. pour tout arc (i, j) faire
4.
si l i 1 v1 i, j2 , l j alors l j d l i 1 v1 i, j2
Le lec teur véri fiera ci après qu’on a bien la numé ro ta tion topologique des som -
mets : pour tout arc (i, j), on a : i , j (cf. fig 4.12 0 ).
La figure 4.12 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. Pour chaque
ité ra tion, le som met en cours de trai te ment est cer clé en épais et les arcs modi fiant
les valeurs l i sont repré
sen tés en gras. Sur la figure en bas à droite, les arcs en traits
doubles sont ceux uti li sés lors de la der
nière modi fi ca tion des valeurs l 1 . En remon -
tant ces arcs nous obte nons un plus court che min issu du som met 1.
Remarque. Nous avons traité jus qu’à présent le cas des che mins de valeur
mini male ; nous allons voir que, dans quelques pro blèmes comme ceux
d'ordonnancement, ce sont, au contraire, les che mins de valeur maximale qui
importent.