Chapitre 3. Le Problème du Plus Court Chemin
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
28
CHAPITRE 3.
LE PROBLEME DU PLUS COURT
CHEMIN.
Les problèmes de cheminement dans les graphes (en particulier la recherche d’un
plus court chemin) comptent parmi les problèmes les plus anciens de la théorie
des graphes et les plus importants par leurs applications.
3.1. DEFINITION.
Soit G = (X, U) un graphe val; on associe à chaque arc u=(i, j) une longueur
l(u) ou l
ij .
Le Problème du plus court chemin entre i et j est de trouver un chemin µ(i, j)
de i à j tel que :
l(µ) =
∑
u
l(u)
soit minimal.
Interprétation de l(µ) : cỏt de transport, dépense de construction, temps
nécessaire de parcours, …
Remarque. La recherche du plus court chemin est analogue à la recherche du
plus long chemin.
Les algorithmes seront différents suivant les propriétés des graphes :
♦ l(u)
≥
0, ∀ u ∈ U.
♦ Les longueurs l(u) égales
⇔
l(u) = 1, ∀ u ∈ U. (problème du plus court
chemin en nombre d’arcs)
♦ G sans circuit.
♦ G et l(u) quelconques.
Chapitre 3. Le Problème du Plus Court Chemin
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
29
Et suivant le problème considéré :
♦ Recherche du plus court chemin d’un sommet à tous les autres,
♦ Recherche du plus court chemin entre tous les couples de sommets.
3.2. PRINCIPE D’ OPTIMALITE.
Le principe d’ optimalité énonce le fait que les sous-chemins des plus courts
chemins sont des plus courts chemins (la programmation dynamique repose sur
ce principe fondamental).
LEMME.
Soient un graphe G(X,U) et une fonction de pondération l : X x X →
R, Soit C = « X
1
, X
2
,…,X
k
» un plus court chemin de X
1
à X
k
et pour tout (i, j)
tel que 1
≤
i
≤
j
≤
k, soit C
ij
= « X
i
, X
i+1
,…,X
j
» un sous chemin de C allant de
X
i
à X
j
. Alors C
ij
est un plus court chemin de X
i
à X
j
.
Principe des algorithmes de recherche de chemins minimaux :
♦ Une distance d(i) est associée à x
i
.
♦ En fin d’algorithme, cette distance représente la longueur d’un plus court
chemin de l’origine au sommet considéré.
3.3. VARIANTES DU PROBLEME : D’ UN SOMMET A TOUS
LES AUTRES.
Ce problème est aussi appelé le problème de recherche du plus court chemin
à origine unique. Beaucoup d’autres problèmes peuvent être résolus par
l’algorithme avec origine unique :
♦ Plus court chemin à destination unique (inversion du sens de chaque arc
du graphe).
♦ Plus court chemin pour un couple de sommets donné.
♦ Plus court chemin pour tout couple de sommets (algorithmes à origine
unique à partir de chaque sommet).
Chapitre 3. Le Problème du Plus Court Chemin
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
30
3.3.1. ALGORITHME DE DIJKSTRA-MOORE (1959).
Supposons que les longueurs des arcs sont non négatives (l(u)
≥
0) and l’ensemble de
n sommets est numéroté de 1 à n. Le problème posé est la recherche du plus court
chemin
entre 1 et tous les noeuds accessibles depuis 1.
Notations :
♦ M = L’ ensemble de noeuds non marqués
♦ Pr(p) = Sommet précédant p sur le plus court chemin de l’origine à p.
♦ d = Plus courte distance de l’origine aux noeds restant. En convention ∝ dans
le cas n’a pas de chemin de l’origin (1) à lui-même.
♦ Mark = L’ensemble des noeuds marqués.
PRINCIPE DE L’ALGORITHME.
1. Au départ du noeud 1. M = {2,…n}
2. À chaque itération, Choisir un noeud à marquer :c’ est le noeud qui a la plus
courte distance.
k = Argmin
x ∈ M
d[x].
Mises à jour d[i], Pr[i] avec i∈ M \{k} à l’aide de la formule:
• d[i] = d[k] + l[k,i] si d[i] > d[k] +l[k,i].
• Pr[i] = k.
Remplacer M := M\{k}.
Si M = ∅. L’ algorithme se termine, sinon retourner à 2.
PROCEDURE DIJKSTRA – MOORE ;
//Suppose que l’ on a la matrice de longuers l est Stocké sous la forme de
matrice d’adjacence
//Initialisations de M, d, Pr, Mark
for (i= 1 ; i≤ n ;i++)
{d[i] = l(1,i) ; pr[i] :=1 ; Mark[i] :=0 ;}
Mark[1] :=1 ; n0 :=n-1 ;
WHILE (n0 > 0)
{
k:= Argmin {d[i] : i∈ M} ;
//Remise à jour d, Pr, M et Mark
Mark[k] :=1 ;
∀ i ∈ M { d[i] := d[k] +l[k,i] si d[i] > d[k] +l[k,i].
Pr[i] = k.}
//Supprimer le noeud k
M := M\{k} ;
}END WHILE ;
Chapitre 3. Le Problème du Plus Court Chemin
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
31
Complexité : O(n²) ou O(mlogn) avec une structure de tas, intéressante si le
graphe est peu dense (i.e., m <<< n²)
L’algorithme de Dijktra-Moore utilise une stratégie gloutonne lorsqu’il choisit le
sommet le moins cỏteux à chaque étape. On démontre que dans le cas de cet
algorithme, cette stratégie conduit à un résultat global optimal.
EXEMPLE .
1
0 Initialisation : M, d, Pr :
1 10 2 M = { 2, 3, 4, 5, 6}
3 d = [0, 10, 3, ∝, 6, ∝]
2 6 4 Pr = [1, 1, 1, 1, 1, 1]
6 0 3
2
1 1
5 3 4
FIG. 3.1. Graphe valué orienté.
1
er
étape. Choisir s
3
. Remise à jour M, d, Pr :
M = { 2, , 4, 5, 6}
d = [0, 7, 3, ∝, 5, ∝]
Pr = [1, 3, 1, 1, 3, 1]
2
è
étape. s
3
est le sommet actuel. Choisir s
5
. Remise à jour M, d, Pr :
M = { 2, , 4, , 6}
d = [0, 5, 3, ∝, 5, 6]
Pr = [1, 5, 1, 1, 3, 5]
3
è
étape. s
5
est le sommet actuel. Choisir s
2
. Remise à jour M, d, Pr :
M = { , , 4, , 6}
d = [0, 5, 3, ∝, 5, 6]
Pr = [1, 5, 1, 1, 3, 5]
4
è
étape. s
2
est le sommet actuel. Choisir s
6
. Remise à jour M, d, Pr :
M = { , , 4, , }
d = [0, 5, 3, ∝, 5, 6]
Pr = [1, 5, 1, 1, 3, 5]
Algorithme se termine car 4 = Argmin {d[i] : i∈ M}; et d[4] = ∝.
À l’issue de la procédure, on obtient le résultat suivant :
Le plus court chemin de s
1
vers s
2
est: s
1
→ s
3
→ s
5
→ s
2
et son cỏt est égal à 5
Le plus court chemin de s
1
vers s
3
est: s
1
→ s
3
et son cỏt est égal à 3
Le plus court chemin de s
1
vers s
5
est: s
1
→ s
3
→ s
5
et son cỏt est égal à 5
Le plus court chemin de s
1
vers s
6
est: s
1
→ s
5
→ s
6
et son cỏt est égal à 6
Chapitre 3. Le Problème du Plus Court Chemin
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
32
On n’a pas trouvé de plus court chemin de s
1
vers s
4
(d[4] = ∝ à la fin), car s
4
est
inaccessible depuis s
1
.
REMARQUE.
L’hypothèse « Les cỏts sont tous positifs ou nuls » est fondamental. L’utilisation de
L’algorithme de Dijktra-Moore pour le graphe de la figure FIG.3.2., où les poids ne
sont pas tous positifs ou nuls, conduit à un resultat incorrect si on choisit comme source
le sommet s
1
. En effet, d’abord on choisit le sommet s
2,
(s
1
→ s
2
) tandis que le
chemin de s
1
vers s
2
passant s
3
est plus court.
3
3 -1
1 2 2
FIG. 3.2. Graphe valué orienté par des cỏts quelconques.
Chapitre 3. Le Problème du Plus Court Chemin
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
33
3.3.2. ALGORITHME DE BELLMAN-FORD (1958-1962)
La présence de longueurs de signes différents (l(u) quelconques), permet par
exemple de modéliser des cỏts et des profits. L’algorithme de DIJKSTRA-
MOORE ne permet pas de considérer les arcs négatifs, car une fois qu’un
sommet est marq on ne peut changer ce marquage lors des itérations suivantes.
L’algorithme de DIJKSTRA-MOORE est ainsi dit à fixation d’étiquettes. On
considère donc ici un algorithme qui permet un marquage qui n’est pas définitif
tant que le programme n’est pas déterminé (le marquage est modifié
itérativement). Ce type d’algorithme est appelé à correction d’étiquettes.
L’ algorithme de BELLMAN-FORD est valable pour des graphes sans circuit,
valués par des longueurs quelconques.
Notations :
♦ S = L’ensemble de n sommets est numéroté de 1 à n.
♦ C = L’ ensemble de noeuds est déjà marq.
♦ M = L’ ensemble de noeuds non marqs (= S\C), pour lesquels les plus
courtes distances ne sont pas encore connues. La plus coute distance de
l’origin à un sommet v ne calcule que lorsque tous les prédécesseurs
de v (Γ
-
(v)) sont dans C.
♦ Pr(p) = Sommet précédant p sur le plus court chemin de l’origine à p.
♦ d = Plus courte distance de l’origine aux autre sommets.
PRINCIPE DE L’ALGORITHME.
1. Initialisations.
Choisir le sommet s
1
pour l’origine.
C = {s
1
} ; M = {s
2
,…,s
n
}.
d[1] = 0.
Pr[1] = 1.
2. À chaque itération :
Choisir un sommet x ∈ M tel que tous les prédécesseurs de x ∈ CC ,
c’est à dire Γ
-
(v) ⊂ C.
Mises à jour CC et M :
C := C ∪ {x} ; M = S\C.
Calculer d[x] = min { d[y] + l[y,x]: y ∈ Γ
-
(x)},
et Pr[x] qui est l’ indice que ce minimun est atteint.
Complexité : O(nm). O(n
3
) pour des graphes denses, i.e., des graphes tels que
m
≈ n².
Chapitre 3. Le Problème du Plus Court Chemin
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
34
EXEMPLE.
3
Initialisation : M, d, Pr :
2 -2 4 M = { 2, 3, 4, 5, 6}, C={1}
d = [0, 10, 3, ∝, 6, ∝]
1 5 -5 Pr = [1, 1, 1, 1, 1, 1]
1 1 6 Γ
-
(2) ={1,3}; Γ
-
(3)={1} ; Γ
-
(4)={2,3,6}
-2 Γ
-
(5) ={3} ; Γ
-
(6) ={2,5}
-1
3 4 5
FIG.3.1. Graphe valué orienté sans circuit de racine s
1
.
1
er
étape. Choisir s
3
car Γ
-
(3)={1} . Remise à jour M, C, d, Pr :
M = { 2, , 4, 5, 6} C= {1,3}
d = [0, , -2, , , ]
Pr = [1, , 1, , , ]
2
è
étape. À cette étape,on aurait pu choisir de supprimer le sommet s
5
au lieu du
sommet s
2
. Remise à jour M, C, d, Pr :
M = { 2, , 4, , 6} C= {1,3,5}
d = [0, , -2, , 2 , ]
Pr = [1, , 1, , 3, ]
3
è
étape. Choisir s
2
. Remise à jour M, C, d, Pr :
M = { , , , 4, , 6} C= {1,2,3,5}
d = [0, -1, -2, , 2 , ]
Pr = [1, 3, 1, , 3, ]
4
è
étape. Choisir s
6
. Remise à jour M, C, d, Pr :
M = { , , , 4, , } C= {1,2,3,5,6}
d = [0, -1, -2, , 2 , 1]
Pr = [1, 3, 1, , 3, 5 ]
5
è
étape. Choisir s
4
. Remise à jour M, C, d, Pr :
M = { , , , , , } C= {1,2,3,4,5,6}
d = [0, -1, -2, -4, 2 , 1]
Pr = [1, 3, 1, 6, 3, 5 ]
Algorithme se termine car M = ∅.
À l’issue de la procédure, on obtient le résultat suivant :
Le plus court chemin de s
1
vers s
2
est: s
1
→ s
3
→ s
2
et son cỏt est égal à -1
Le plus court chemin de s
1
vers s
3
est: s
1
→ s
3
et son cỏt est égal à -2
Le plus court chemin de s
1
vers s
4
est: s
1
→ s
3
→ s
5
→ s
6
→ s
4
et son cỏt est
égal à –4.
Le plus court chemin de s
1
vers s
5
est: s
1
→ s
3
→ s
5
et son cỏt est égal à 2
Le plus court chemin de s
1
vers s
6
est: s
1
→s
3
→ s
5
→ s
6
et son cỏt est égal à 1
Chapitre 3. Le Problème du Plus Court Chemin
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
35
3.4. ENTRE TOUS LES COUPLES DE SOMMETS : ALGORITHME DE
FLOYD (algorithme matriciel) (1962).
On va ainsi calculer un distancier n x n. Si tous les arcs sont tous de longueur
positive ou nulle (l(u)
≥ 0), on peut appliquer n fois l’algorithme de Dijktra-
Moore pour chaque sommet i. Si le graphe comporte des arcs de longueur
strictement négative, on peut appliquer n fois l’algorithme de Bellman-Ford.
L’algorithme de Floyd constitue une autre approche qui peut être avantageuse
principalement par rapport à la seconde solution, qui nécessite un temps
d’exécution en O(n
4
) pour des graphes denses. Contrairement aux algorithmes à
origine unique qui supposent que le graphe est représenté par une liste
d’adjacence, l’algorithme de Floyd (algorithme de programmation dynamique)
utilise une représentation par matrice d’adjacence.
Soient les matrices : L = [l
ij
] ; P = [p
ij
].
l
ij
= l(i, j) si (i, j) ∈ U
=
∞ sinon
l
ii
= 0.
l
ii
= 0
p
ij
= 0 si l
ii
=
∞
p
ij
= i sinon.
En fin d’algorithme :
p
ij
= prédécesseur de j sur le plus court chemin de i à j.
l
ij
= longueur du plus court chemin entre i et j.
PROCEDURE FLOYD (L, P)
For (k=1 ; k≤ n ; k++)
For (i=1 ; i≤ n ; i++)
For (j=1 ; j≤ n ; j++)
IF (l[i,k] + l[k,j] < l[i,j])
{l[i,j] = l[i,k] + l[k,j] ; p[i,j] =p[k,j]}
Complexité : O(n
3
).
Chapitre 3. Le Problème du Plus Court Chemin
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
36
EXEMPLE .
1 2 2
-1
6 -2
-4 5
4 5 3
Initialisation : les matrices L, P.
1 2 3 4 1 2 3 4
1 0 2 ∝ 6 1 1 0 1
L
0
= 2 ∝ 0 -2 ∝ P
0
= 0 2 2 0
3 ∝ 5 0 5 0 3 3 3
4 -4 -1 ∝ 0 4 4 0 4
Les étapes :
k =1.
1 2 3 4 1 2 3 4
1 0 2 ∝ 6 1 1 0 1
L
1
= 2 ∝ 0 -2 ∝ P
1
= 0 2 2 0
3 ∝ 5 0 5 0 3 3 3
4 -4 -2 ∝ 0 4 1 0 4
k = 2
1 2 3 4 1 2 3 4
1 0 2 0 6 1 1 2 1
L
2
= 2 ∝ 0 -2 ∝ P
2
= 0 2 2 0
3 ∝ 5 0 5 0 3 3 3
4 -4 -2 -4 0 4 1 2 4
k =3
1 2 3 4 1 2 3 4
1 0 2 0 5 1 1 2 3
L
3
= 2 ∝ 0 -2 3 P
3
= 0 2 2 3
3 ∝ 5 0 5 0 3 3 3
4 -4 -2 -4 0 4 1 2 4
k = 4
1 2 3 4 1 2 3 4
1 0 2 0 5 1 1 2 3
L
4
= 2 -1 0 -2 3 P
4
= 0 2 2 3
3 1 3 0 5 4 1 3 3
4 -4 -2 -4 0 4 1 2 4
Chapitre 3. Le Problème du Plus Court Chemin
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
37
Obtention des plus court chemin.
Pour obtenir un plus court chemin de s
I
à s
j
, il suffit d’utiliser la ligne numéro i de
la matrice P. Par exemple, si on veut obtenir le plus court chemin µ de s
4
à s
3
, on
consulte la matrice P ainsi : P[4,3]=2 :s
2
est donc le prédécesseur de s
3
; P[4,2]=1 :
s
1
est donc le prédécesseur de s
2
; P[4,1]=4 :s
4
est donc le prédécesseur de s
1
Finallement
le chemin
µ = s
4
→ s
1
→ s
2
→ s
3
.
L’algorithme utilisé est celui de Floyd (dans une application de recherche de la
fermeture transitive d’un graphe, cet algorithme a été développé par Warshall la
même année (1962) ; cet algorithme est donc souvent appelé « Floyd-
WARSHALL ».
PROCEDURE FLOYD-WARSHALL (L, P)
Soient les matrices : L = [l
ij
] ; P = [p
ij
].
l
ij
= 1 si (i, j) ∈ U
= 0 sinon
p
ij
= 0 si l
ii
= 0
p
ij
= i sinon.
PROCEDURE FLOYD-WARSHALL (L, P)
For (k=1 ; k≤ n ; k++)
For (i=1 ; i≤ n ; i++)
For (j=1 ; j≤ n ; j++)
IF (l[i,j] = = 0)
{l[i,j] = l[i,k] *l[k,j] ; p[i,j] =p[k,j] ;}
Complexité : O(n
3
).
EXEMPLE .
Không có nhận xét nào:
Đăng nhận xét