Chapitre 3 :

RecheRche d’un

chemin

de

valeur optimale

1
III.1 GRAPHE VALUE
1) Définitions

a) Un graphe G est dit valué si à chacun de ses arcs on affecte

une valeur positive appelée longueur ou valeur de l’arc.
Cette valeur est soit un temps, une distance, un coût ou une
quantité de matière.

Exemple

3 3
4
4 5
2 1
4 4 7
1
2
2 4 1 1
5
4 6

b) La longueur d’un chemin est la somme des longueurs des

arcs qui le composent (au sens des longueurs et non plus au
sens des arcs).

Sur l’exemple, le chemin (1,4,3,7) a pour longueur :

 3 au sens des arcs

 9 au sens des longueurs.
c) Associer une longueur à un arc (x,y) revient à définir une
application de l’ensemble des arcs  vers l’ensemble des
réels positifs stricts 𝐿(x, y) et la longueur du chemin
(x1,x2,…,xn) est alors : ∑𝑛−1
𝑖=1 L( xi , xi+1 )

2
2) Représentations d’un graphe Valué

1.- Matrice des valeurs

Autre que la représentation sagittale, on peut représenter un graphe
valué par une matrice des valeurs V dont les coefficients sont les
longueurs ou les valeurs des arcs qui ont pour origine le numéro de la
ligne et pour extrémité le numéro de la colonne.
Sur l’exemple précédent, on utilise la matrice V:
0 0 4 0 0 0 4
4 0 0 2 4 0 0
0 0 0 0 0 0 5
1 0 3 0 0 0 0
1 0 0 0 0 4 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
2.- Matrice des coûts
On peut aussi représenter un graphe valué par une matrice des coûts
dont les coefficients C dont les coefficients sont définis comme
suit :
0 𝑠𝑖 𝑗 = 𝑗
C(i, j) = { +∞ 𝑠𝑖 𝑖 ≠ 𝑗 𝑒𝑡 (𝑖, 𝑗) 𝑛′ 𝑒𝑠𝑡 𝑝𝑎𝑠 𝑢𝑛 𝑎𝑟𝑐
𝑣𝑎𝑙 (𝑖, 𝑗) 𝑠𝑖 𝑖 ≠ 𝑗 𝑒𝑡 (𝑖, 𝑗) 𝑒𝑠𝑡 𝑢𝑛 𝑎𝑟𝑐.

III.2 RECHERCHE D’UN CHEMIN DE LONGUEUR

OU VALEUR OPTIMALE (Minimale ou Maximale)
Problème
Soit G un graphe à n sommets x1,x2,…,xn ; on se donne deux
sommets quelconques du graphe x et y et se propose de
déterminer le chemin le plus long ou le plus court d’origine x
et d’extrémité y.
Deux types d’algorithmes sont utilisés

3
 A. Si le graphe est sans circuit
1. Algorithme des Marques
Ce problème n’a de sens que si le graphe est sans circuit; sinon il est
possible de trouver un chemin plus long en repassant par les mêmes
sommets.
i- Exemple de Présentation
ii- Soit le graphe suivant ordonné par niveaux (donc sans
circuit).
Ple : On cherche le chemin le plus long ayant pour origine 4 et pour
extrémité 7.
3 7
2

4 6 3 6 3
3 5 6
9
1 5
2 1 9 8
4 2 5
5 8

C0 C1 C2 C3 C4 C5
Etape 1 : réduction du graphe
 Supprimer du graphe les sommets de niveau inférieur ou égal au
niveau de 4 et les arcs dont ces sommets sont origine ou
extrémité
 Supprimer du graphe les sommets de niveau supérieur ou égal au
niveau de 7 et les arcs dont ces sommets sont origine ou
extrémité
Etape 2 : Détermination de la marque de chaque sommet et
Détermination du chemin le plus long
Dans le graphe résultant, On affecte à chaque sommet x une marque
m(x) définie de la manière suivante :
1. Pour le sommet initiale de niveau 0 dans le nouveau graphe
m(x)=0(ici x =4 ; m(4)=0)

4
 2. Pour les sommets y de niveaux suivants supérieurs, on calcule
m(y) par : m(y)=Max(m(x)+L(x,y)) pour x appartenant à
l’ensemble des précédents de y.
3. On réitère cette procédure jusqu’à ce qu’on a calculé la fonction
m de tous les points et on arrive à celle du sommet 7.
M(7) = longueur du chemin le plus long cherché d’origine 4 et
d’extrémité 7.
Etape 3 : Détermination du chemin de valeur ou longueur maximale
On se place au sommet 7 et on cherche parmi ces prédécesseurs
, quel est celui dont la marque m(x) se déduit de celle de la
marque m de 7 en retranchant la valeur de l’arc qui le relie à 7 ;
on se place alors sur ce nouveau sommet sélectionné et on répète
le même procédé jusqu’à ce que ce qu’on atteint le sommet origine
4.
La liste des sommets sélectionnés constitue alors le chemin
cherché.
Application
Etape 1
Sommets à supprimer : 1,2,8 et 9
Arcs à supprimer : (1,2) ;(1,4) ;(2,3) ;(2,7) ;(7,9) ;(6,8) ;(5,8) ;(8,9)

3 6
3 5 6
5
1
4 2 5

m(4)=0 ;
m(3)=5 ;
m(5)=2 ;
m(6)=max(m(3)+5;m(5)+1)=10 ;
m(7)=max(m(3)+3;m(6)+6)=16

5
le plus long chemin d’origine 4 et d’extrémité 7 a pour longueur 16
Détermination chemin le plus long d’origine 4 et d’extrémité 7 :
On se place au sommet 7 ; ses précédents sont :3 et 6
M(3)=m(7)-val(3,7) ? Non
M(6)=m(7)-val(6,7) ? Oui
On se place au sommet 6 ; ses précédents sont :3 et 5
M(3)=m(6)-val(3,6) ? Oui
M(5)=m(6)-val(5,6) ? Non
On se place au sommet 3 ; ses précédents sont :4
M(4)=m(3)-val(4,3) ? Oui
Le chemin don cherché est (4,3,6,7) de longueur maximale 16.

2. Algorithme de FORD-BELLMANN
On suppose que le graphe est sans circuit.
L’algorithme s’exécute en 4 étapes :
i- Numéroter les sommets du graphe dans un ordre quelconque
avec x0 le sommet origine et xn le sommet extrémité.
Soit (n+1) le nombre total de sommets du graphe.
ii- On affecte provisoirement à tout sommet xi (i#0) une
quantité positive ou nulle 𝑖 = +∞ ( respectivement 𝑖 = 0
pour le problème du maximum)
On pose pour x0 = +∞ 0 = 0

iii- On calcule les quantités 𝑗 de proche en proche, en fonction

des différences 𝑗 − 𝑖 s’il existe un arc (x𝑖 , x𝑗 ), par les
formules suivantes :
 𝑗 = 𝑖 + 𝑣𝑎𝑙(x𝑖 , x𝑗 ) si 𝑗 − 𝑖 > 𝑣𝑎𝑙(x𝑖 , x𝑗 ) pour le pbe du
minimum
 𝑗 = 𝑖 + 𝑣𝑎𝑙(x𝑖 , x𝑗 ) si 𝑗 − 𝑖 < 𝑣𝑎𝑙(x𝑖 , x𝑗 ) pour le pbe du
maximum
iv- On arrête l’algorithme lorsqu’aucun des 𝑖 n’est plus modifié !

i- Exemple de Présentation
Soit le graphe suivant ordonné par niveaux (donc sans circuit).

6
 Ple : On cherche le chemin le plus court ayant pour origine A et
pour extrémité G.
3
B
C
2 2 5
4 F 4 G
A
3 1 7
D 1 E

1ère Etape
x0=A , x1=B, x2=C ,x3=D, x4=E, x5=F, x6=G
2ème Etape
0=0, 1=2=3=4=5=6=+∞
3ème Etape
De x0 : (x0 , x1); (x0 , x3)
 1 = 0 + 𝑣𝑎𝑙(x0 , x1 ) = 0 + 2 = 2 car
1 − 0 = +∞ − 0 = +∞ > 𝑣𝑎𝑙(x0 , x1 ) = 2
 3 = 0 + 𝑣𝑎𝑙(x0, x1 ) = 0 + 3 = 3 car
3 − 0 = +∞ − 0 = +∞ > 𝑣𝑎𝑙(x0 , x1 ) = 3
Donc
0=0 , 1=2;3=3;2=4=5=6=+∞

De x1 : (x1 , x2); (x1 , x3 ) ; (x1 , x4 )

 2 = 1 + 𝑣𝑎𝑙(x1 , x2 ) = 2 + 3 = 5 car
2 − 1 = +∞ − 2 = +∞ > 𝑣𝑎𝑙(x1 , x2 ) = 3
 3 = 3 car 3 − 1 = 3 − 2 = +1 < 𝑣𝑎𝑙(x1 , x3 ) = 4

 4 = 1 + 𝑣𝑎𝑙(x1 , x4 ) = 2 + 2 = 4 car
4 − 1 = +∞ − 2 = +∞ > 𝑣𝑎𝑙(x1 , x2 ) = 2
Donc
0=0 , 1=2;2=5;3=3 ;4=4 ;5=6=+∞

De x2 : (x2 , x5 )

7
 5 = 2 + 𝑣𝑎𝑙(x2, x5 ) = 5 + 5 = 10 car
5 − 2 = +∞ − 5 = +∞ > 𝑣𝑎𝑙(x2 , x5 ) = 5
Donc
0=0 , 1=2;2=5;3=3 ;4=4 ;5=10 ;6=+∞

En continuant de la même façon et avec la même procédure ; on

trouve :

0=0 , 1=2;2=4;3=3 ;4=4 ;5=9 ;6=13

3ème Etape : Détermination du chemin de valeur minimale

On procède comme la dernière étape de l’algorithme des marques.

B. Si le graphe est contient des circuits

Algorithme de DIJKSTRA
Cet algorithme permet de donner tous les chemins de longueur
minimale d’origine un sommet quelconque choisi du graphe qu’on
notera x1 ou simplement 1 et d’extrémité tout autre sommet du
graphe.
L’algorithme s’exécute en deux phases :
. Phase d’initialisation
. Phase de traitement
Le résultat cherché est un donc un vecteur noté
=((1), (2),…, (n))
Tel que (i) soit égal à la longueur du plus court chemin de 1 au
sommet i.
On initialise ce vecteur (i) à C(1,i) pour i=1,2,…,n
soit =((1), (2),…, (n)) la première ligne de la matrice des
coûts du graphe C.
avec (i)=C(1,i) où C est la matrice des coûts du graphe.

8
On considère deux ensembles de sommets S initialisé à {1} et 𝑆 −
Son complémentaire dans X ensemble des sommets du graphe.
A chaque pas de l’algorithme, on ajoute à S des sommets jusqu’à ce
que le vecteur  donne à chaque étape le coût minimal des
chemins de 1 aux sommets de S.

Description de l’algorithme
Initialisations
= C(1,i) pour i=1,2,…n
S={1} et 𝑆 − ={2,3,…,n}
Itérations
Tant que 𝑆 − ≠ ∅ faire
 Choisir i dans 𝑆 − tel (i) est minimum
 Retirer i de 𝑆 − et l’ajouter à S
 Pour chaque successeur j de i dans 𝑆 − faire
(j) = min((j), (i)+val(i,j))
Fait
Fait
Exemple
Appliquer l’algorithme de DIJKSTRA au graphe suivant pour
déterminer tous les Chemins de valeur minimale du sommet 1 à tous
les autres sommets du graphe.
2

15
3 3

1
10
4

5 5

7 3 2

9
 Appliquons l’algorithme de DIJKSTRA au graphe ci-dessous :

Initialisation

S={1} ; 𝑆 − ={2,3,4,5} ;  =(0,15,,,4)

1ère Itération :
i=5 car (5)=min(15,,,4)=4
S={1,5} ; 𝑆 − ={2,3,4}
Les successeurs de 5 dans 𝑆 − 3 et 4
(3)=min(,4+7)=11 ; (4)=min(,4+5)=9
Le nouveau vecteur  =(0,15,11,9,4)

2ème Itération :
I=4 car (4)=min(15,11,9)=9
S={1,4,5} ; 𝑆 − ={2,3}
Le nouveau vecteur  =(0,12,11,9,4)

3ème Itération :
I=3 car (3)= 11
S={1,3,4,5} ; 𝑆 − ={2}
Le nouveau vecteur  =(0,12,11,9,4)

4ème Itération :
I=4 car (2)=12
S={1,2,3,4,5} ; 𝑆 − =∅
Le nouveau vecteur  =(0,12,11,9,4)
Le chemin minimal de 1 à 4 par exemple est de coût 9, c’est le chemin
(1,5,4)

10