LE PROBLEME DU PLUS COURT CHEMIN
Les problèmes de cheminement (itinéraire, parcours ou chemin) 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.
I. DEFINITION :
Soit G = (X, U) un graphe valué (pondéré) ; on associe à chaque arc u=(i, j) une longueur l(u) ou lij.
Le Problème du plus court chemin entre i et j est de trouver un chemin μ(i, j) de i à j tel que :
l(μ) = ∑ l(u) où u ∈ μ soit minimal.
Interprétation de l(μ) : coût de transport, dépense de construction, temps nécessaire de parcours...
II. PRINCIPE D’OPTIMALITE :
Le principe d’optimalité énonce le fait que les sous-chemins des plus courts chemins sont des plus
courts chemins. Si le plus court chemin PAB de A à B passe par le nœud C, alors la portion PAC est un
plus court chemin de A à C.
Principe des algorithmes de recherche de chemins minimaux :
- Une distance d(i) est associée au sommet i.
- En fin d’algorithme, cette distance représente la longueur d’un plus court chemin de l’origine
au sommet i.
III. D’UN SOMMET A TOUS LES AUTRES :
Ce problème est aussi appelé le problème de recherche du plus court chemin à origine unique.
Si dans le graphe, il existe un circuit de longueur négative (circuit absorbant), la recherche d’un plus
court chemin de l’origine au sommet considéré est sans objet. En effet, on peut utiliser le circuit une
infinité de fois (entrainant la diminution perpétuelle de la longueur du chemin).
1. ALGORITHME DE MOORE DIJKSTRA
L'algorithme de Dijkstra sert à résoudre le problème du plus court chemin à partir d'une source vers
tous les autres sommets dans un graphe orienté pondéré par des réels positifs.
Notation :
Si i ∈ X alors :
- Γ(i) : ensemble des successeurs de i
- Γ-1(i) : ensemble des prédécesseurs de i
- PCC(i) : longueur du plus court chemin d’un sommet source s à i
- X : ensemble des sommets dans le graphe
- S : un ensemble des sommets non visités (non marqués)
Algorithme :
Etape 1 : Initialisation
Choisir le sommet origine s
S = X – {s}
PCC(s) = 0
𝑙(𝑠, 𝑖) 𝑠𝑖 𝑖 ∈ Γ(s)
PCC(i) = {
∞ 𝑠𝑖𝑛𝑜𝑛
Etape 2 :
Sélectionner j ∈ S tel que : PCC(j) = min (PPC(i)) où i ∈ S
Faire S = S – {j}
Si S = {} alors STOP
Sinon aller à l’étape 3
Etape 3 :
Pour tout i ∈ Γ(j) ∩ S
Faire PCC(i) = min (PCC(i) ; PCC(j) + l(j, i))
Retourner à l’étape 2
Application :
j=s=A
S = {B, C, D, E, F, G}
PCC(A) = 0
PCC(B) = 2
PCC(C) = 7
PCC(D) = ∞
PCC(E) = ∞
PCC(F) = ∞
PCC(G) = ∞
j=B
S = S – {B} = {C, D, E, F, G}
Γ(B) = {C, D}
Γ(B) ∩ S = {C, D}
PCC(C) = min (PCC(C), PCC(B) + l(B, C)) = min (7, 2 + 5) = 7
PCC(D) = min (PCC(D), PCC(B) + l(B, D)) = min (∞, 2 + 3) = 5
j=D
S = S – {D} = {C, E, F, G}
Γ(D) = {C, E, F}
Γ(D) ∩ S = {C, E, F}
PCC(C) = min (PCC(C), PCC(D) + l(D, C)) = min (7, 5 + 1) = 6
PCC(E) = min (PCC(E), PCC(D) + l(D, E)) = min (∞, 5 + 6) = 11
PCC(F) = min (PCC(F), PCC(D) + l(D, F)) = min (∞, 5 + 7) = 12
j=C
S = S – {C} = {E, F, G}
Γ(C) = {E, G}
Γ(C) ∩ S = {E, G}
PCC(E) = min (PCC(E), PCC(C) + l(C, E)) = min (11, 6 + 5) = 11
PCC(G) = min (PCC(G), PCC(C) + l(C, G)) = min (∞, 6 + 2) = 8
j=G
S = S – {G} = {E, F}
Γ(G) = {E, F}
Γ(G) ∩ S = {E, F}
PCC(E) = min (PCC(E), PCC(G) + l(G, E)) = min (11, 8 + 2) = 10
PCC(F) = min (PCC(F), PCC(G) + l(G, F)) = min (12, 8 + 4) = 12
j=E
S = S – {E} = {F}
Γ(E) = {F}
Γ(E) ∩ S = {F}
PCC(F) = min (PCC(F), PCC(E) + l(E, F)) = min (12, 10 + 1) = 11
j=F
S = S – {F} = {} => STOP
j\i A B C D E F G
A 0 2 7 ∞ ∞ ∞ ∞
B 0 2 7 5 ∞ ∞ ∞
D 0 2 6 5 11 12 ∞
C 0 2 6 5 11 12 8
G 0 2 6 5 10 12 8
E 0 2 6 5 10 11 8
