Chapitre Fiche 3.

Recherche opérationnelle et optimisation Yassine Hachaı̈chi

Plus court chemin

1 Graphes valués

1.1 Distance
Définition 1.1 Soit G = (X; A) un graphe orienté. Pour tout (x; y) ∈ X 2 ; la distance entre le sommet x et le
sommet y est le nombre d(x; y) défini par : d(x; y) = ∞ s’il n’existe pas de chemin de x à y min{l(c)|c est un
chemin de x à y}
l(c) désigne la longueur du chemein c : La matrice des distances du graphe G est la matrice D = (di;j ) =
(d(xi ; xj )).
Algorithme de Moore
Soit x et y deux sommets d’un graphe G = (X; A). L’algorithme suivant calcule la distance d(x; y).
On étiquette les sommets de G en observant les règles suivantes :
le sommet x reçoit l’étiquette 0
si (u; v) ∈ A et u est étiqueté k :
i. si v n’est pas étiqueté, alors v reçoit l’étiquette k + 1
ii. si v est étiqueté l ; alors l’étiquette de v est remplacée par min(l; k + 1)
Si, à la fin, y à une étiquette k ; alors d(x; y) = k ; sinon d(x; y) = 1.
Remarque :
lorsque d(x; y) = k ; l’algorithme précédent permet d’exhiber de façon récursive les chemins de longueur k de
x à y : on part de y et on détermine les sommets z tels que (z; y) ∈ A avec d(x; z) = k − 1 et ainsi de suite
jusqu’en x.

1.2 Graphes valués et problème du plus court chemin

Beaucoup de problèmes peuvent être modélisés en utilisant des graphes valués. Les problèmes de cheminement
dans les graphes, en particulier la recherche du plus court chemin, comptent parmi les problèmes les plus
anciens de la théorie des graphes et les plus importants par leurs applications : coût de transport, temps de
parcours, problème de trafic,. . . Les algorithmes de recherche de plus court chemin seront différents selon les
caractérisitiques du graphe.

Définition 1.2 Un graphe valué est un graphe orienté G = (X; A) ; muni d’une fonction c : A → R ; appelée
fonction de coût.
Remarque :
On peut également définir la notion de graphe valué non orienté. La fonction de coût représente le coût de
transport, dépense de construction, temps nécessaire de parcours, etc.
Exemple :
Graphe valué de modélisation d’un réseau aérien

1
2 Graphes et Applications

Définition 1.3 Le coût d’un chemin est la somme des coûts des arcs de ce chemin. On peut définir la matrice
des coûts du graphe, c’est la matrice C = (ci;j ) où :


 0 si i=j
ci;j = ∞ si i ̸= j et (xi ; xj ) ∈
/A


c(xi ; xj ) si i ̸= j et (xi ; xj ) ∈ A

On a alors :
∑
n−1
c(x0 , · · · , xn ) = c(xi , xi+1 ) = c(x0 , · · · , xi ) + c(xi , · · · , xn )
i=0

Un circuit absorbant est un circuit (x, x0 , · · · , xn , x) de coût négatif.

Définition 1.4 Soit G = (X; A; c) un graphe valué, x et y deux éléments de X. Une chemin ch de G de x à y
est dit minimum lorsque pour tout chemin ch′ de G allant de x à y on a : c(ch′ ) ≥ c(ch). On définit la matrice
M = (mi;j ) de coût minimum par :


 0 si i = j
mi;j = ∞ s’il n’existe pas de chemin de x à y


min{c(ch)|ch est un chemin de x à y

Proposition 1.1 Si a1 , a2 , · · · sont des arcs et si a1 , a2 , · · · , ai , · · · , aj , · · · ap est un chemin de valeur minimale

du sommet s vers le sommet s′ , alors tout sous-chemin ai , · · · , aj est minimal entre les sommets x, origine de
ai et y, but de aj .
L’explication est simple : si le sous-chemin ai , · · · , aj n’est pas minimal, alors en le remplaçant par un autre
chemin ai , · · · , ak , · · · , aj de valeur moindre, on obtient un chemin de plus petite valeur de s vers s′ , ce qui
contredit l’hypothèse et est absurde.
Décrivons à présent deux algorithmes de recherche de chemin minimum.

1.3 Algorithme de Dijkstra ( 1959 )

Cet algorithme ne fonctionne que pour les graphes valués positivement.
Numérotons les sommets du graphe de 1 à n : Cet algorithme calcule le plus court chemin du sommet 1 à tous
les sommets du graphe ( il donnera donc la première ligne de la matrice de coût minimum ).
On construit un vecteur U = (U (1); U (2); · · · ; U (n)) ayant n composantes tel que U (i) soit égal à la longueur
du plus court chemin allant de 1 au sommet i, et un vecteur P = (P (1); P (2); · · · ; P (n)) ayant n composantes
tel que P (i) soit égal au prédécesseur de i dans le plus court chemin de 1 à i. On initialise le vecteur U à (c1;i ) ;
c’est-à-dire à la première ligne de la matrice des coûts du graphe ; et le vecteur P à (1, · · · , 1). On considère
ensuite deux ensembles de sommets, S initialisé à {1} et S son complémentaire dans X ; ensemble des sommets
du graphe. à chaque pas de l’algorithme, on ajoute à S des sommets jusquà ce que S = X de telle sorte que le
vecteur U donne à chaque étape le coût minimal des chemins de 1 aux sommets de S.
Description de l’algorithme :
initialisations
U = (c1;i ) pour i = 1; 2; · · · ; n.
P = (1, · · · , 1)
Y. Hachaı̈chi 3

S = {1}; S = {2; 3; · · · ; n}
itérations
Tant que S ̸= ∅ ;
Choisir i dans S tel que U (i) est minimum
Retirer i de S et l’ajouter à S
Pour chaque successeur j de i dans S,
Si U (j) > U (i) + c(i; j) Alors U (j) := U (i) + c(i; j) ;
P (j) := i Finsi ; FinTQ.
Exemple : Appliquons l’algorithme de Dijkstra au graphe représenté par la matrice suivante :
 
0 15 ∞ ∞ 4
 
 ∞ 0 ∞ ∞ ∞ 
 
 ∞ 3 0 2 ∞ 
 
 
 10 3 ∞ 0 ∞ 
∞ ∞ 7 5 0

Initialisation S = {1}; S = {2; 3; 4; 5}; U = (0; 15; ∞; ∞; 4)

1re itération : i = 5 car U (5) = min(15; ∞; ∞; 4) = 4
S = {1; 5}; S = {2; 3; 4} ; les successeurs de 5 dans S sont 3 et 4,
U (3) prend la nouvelle valeur min(∞; U (5) + c(5; 3)) = min(∞; 4 + 7) = 11;
U (4) prend la nouvelle valeur min(∞; U (5) + c(5; 4)) = 9 ; d’où les nouveaux vecteurs U = (0; 15; 11; 9; 4) et
P = (1, 1, 5, 5, 1).
2e itération : i = 4; U (4) = 9; S = {1; 5; 4}; S = {2; 3}; U = (0; 12; 11; 9; 4) et P = (1, 4, 5, 5, 1).
3e itération : i = 3; U (3) = 11; S = {1; 5; 4; 3}; S = {2}; U = (0; 12; 11; 9; 4)
4e itération : i = 2; U (2) = 12; S = {1; 5; 4; 3; 2} = X; S = ∅; U = (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 :
Remarque
Si G = (X; A) est un graphe orienté, on peut considérer la fonction de coût :
c : A → {1} tel que c(a) = 1 pour tout a ∈ A.
Le coût d’un chemin du graphe G ainsi valué par c est la longueur de ce chemin.
L’algorithme de Dijkstra dans ce cas particulier est en fait l’algorithme de Moore.
Preuve de l’algorithme On commence par classer les sommets selon leur distance à x0 : S = {x0 , · · · , xn }

0 = d(x0 , x0 ) ≤ d(x0 , x1 ) ≤ · · · ≤ d(x0 , xn )

On fait une démonstration par récurrence.

Initialisation : Les propriétés sont vraies pour i = 0 :c’est la phase d’initialisation de l’algorithme.
Hérédité : On suppose les propriétés vraies pour tout rang jusqu’à i, montrons la au rang i + 1.
Soit xk un prédécesseur de xi le long d’un plus court chemin de x0 à xi . La distance de x0 à xk est d(x0 , xi ) −
v(xk , xi ), qui est plus petite que d(x0 , xi ) car tous les arcs sont de valuation positive. Par conséquent xk est
classé avant xi : k < i.
4 Graphes et Applications

Par hypothèse de récurrence xk a été marqué pendant la (k + 1) ième itération, à la sortie de laquelle on a
d(xk ) = d(x0 , xk ) et d(xi ) = d(xk ) + v(xk , xi ) = d(x0 , xi ).
A la (i + 1) ème itération on a alors pour tout sommet non marqué xj , j > i : d(xi ) = d(x0 , xi ) < d(x0 , xj ) ≤
d(xj ). Le sommet xi est donc celui qui est marqué à la (i + 1) ème itération et il vérifie bien d(xi ) = d(x0 , xi ).

1.4 Algorithme de Bellman-Ford

Cet algorithme fonctionne aussi bien pour les graphes à valuation positive que quelconque.
Remarque :
Dans un graphe valué dans R, l’existence d’un plus court chemin entre i et j, dépend de l’existence d’un chemin
entre ces sommets et de l’absence de circuits absorbants.

Proposition 1.2 S’il existe un plus court chemin entre deux sommets x et y, alors il existe un plus court
chemin élémentaire entre x et y.
Soit C0 = (x0 , x1 , · · · , xn ) un plus court chemin entre x0 et xn .
Si C0 n’est pas élémentaire, il existe deux indices p et q, 0 ≤ p < q ≤ n,tels que xp = xq .
Le sous-chemin C1 = (xp , · · · , xq ) est alors un circuit,et c’est aussi un plus court chemin d’après la propriété
précedente. Il est donc au moins aussi court que le chemin trivial (xp ), de valuation 0.
Si la valuation de C1 est strictement négative, alors C1 est un circuit absorbant, et il n’existe pas de plus court
chemin entre x0 et xn , ce qui est absurde.
On notera S l’ensemble des sommets.

Initialisation :
d(x0) = 0,P(x0)=x0;
pour tout s dans S, s =/=x0
repeter
d(s)= c(x0,s),
P(s)=x0
fin=FAUX
tant que fin=FAUX repeter
fin := VRAI
pour tout x dans S repeter
pour tout y successeur(x) repeter
si d(x)+c(x,y)<d(y) alors
d(y):= d(x)+c(x,y)
P(y) := x
fin := FAUX
fin tant que

Preuve de l’algorithme Si un plus court chemin élémentaire de x0 à un sommet s comporte k arcs, alors après
k passages dans la boucle on a d(s) = d(x0, s).
On fait une récurrence sur le nombre d’arcs k d’un plus court chemin élémentaire.
Initialisation : La propriété est vraie pour k = 0 : c’est la phase d’initialisation de l’algorithme.
Y. Hachaı̈chi 5

Hérédité : On suppose la propriété vraie au rang k−1, montrons-la au rang k. Soit p le prédécesseur de s le long du
plus court chemin élémentaire comportant k arcs de x0 à s. Il existe un plus court chemin élémentaire comportant
k1 arcs de x0 à p, donc par hypothèse de récurrence, après k − 1 passages dans la boucle on a d(p) = d(x0 , p).
Après le k-ième passage dans la boucle, on a alors d(s) = d(p) + c(p, s) = d(x0 , p) + c(p, s) = d(x0 , s).
L’algorithme permet de détecter la présence de circuits absorbants : si les valeurs d(s) ne sont pas stabilisées
après n passages de boucles, alors le graphe contient au moins un circuit absorbant.
On peut améliorer légèrement l’algorithme en ne regardant que les successeurs des sommets ayant été modifiés
récemment.

Initialisation :
d(x0) = 0,P(x0)=x0;
pour tout s dans S, s =/=x0
repeter
d(s)= c(1,s),
P(s)=x0
L := {x0}
tant que L non vide repeter
choisir x Dans L
L := L-{x}
pour tout y Successeur(x) repeter
si d(x)+c(x,y)<d(y)alors
d(y) := d(x)+c(x,y)
P(y) := x
L := L + {y}
fin tant que

1.5 Algorithme de Floyd Warshall

On utilise une matrice carrée M d’ordre n initialisée par les valeurs c(i, j).
On utilise une matrice carrée P d’ordre n dans laquelle Pi,j sera le père de j dans un plus court chemin depuis
i.
initialisations
Pour i:=1 à n faire
Pour j:=1 à n faire
Mi,j := c(i, j) ET Pi,j := i finpour finpour
itérations
Pour k de 1 à n faire
Pour i de 1 à n faire
Pour j de 1 à n faire
si Mi,k + Mk,j < Mi,j alors Mi,j := Mi,k + Mk,j ; Pi,j := Pk,j finsi
finpour finpour finpour
finprocédure
6 Graphes et Applications

Preuve de l’algorithme
La matrice M initiale contient les plus courts chemins de i à j ne passant par aucun autre sommet. On peut
montrer par récurrence qu’à l’étape k, Mi,j est égal à un plus court chemin de i à j passant uniquement par les
sommets 1, · · · , k. Cela constitue l’invariant de la boucle pour.