31
Chapitre 4 : Problème du plus court chemin
I. Introduction
Ce problème intervient principalement dans le fonctionnement des routeurs d’un
réseau informatique (protocoles de routage). La recherche du plus court chemin est
analogue à la recherche du plus long chemin.
II. Définition
Soit G=(X,U) un graphe valué, l’interprétation de la valeur de chaque arc peut être:
coût de transport,distance, dépense de construction,temps nécessaire de parcours, ...
▪ La longueur d’un chemin entre deux sommet x et y dans un graphe valué est :
𝐿𝑜𝑛𝑔𝑢𝑒𝑢𝑟_𝐶ℎ (𝑥, 𝑦) = ∑ 𝑓(𝑢)
𝑢 𝜖 𝐶ℎ
tel que f(u) est la fonction qui fournit la valeur de l’arc u.
▪ La distance, notée dG (x , y), entre deux sommets d’un graphe G est la longueur
du plus court chemin entre les extrémités x et y. S’il n’y a pas de chemin entre x
et y on considère que d (x , y) = ∞
Nous verrons dans la partie algorithmique les méthodes de calculs de cette
distance :
[Link] 8 : Algorithme de Dijkstra
Algorithme 8 :permettant de trouver le plus court chemin
entre deux sommet Sdeb et Sfin
Entrée: G=(X;U)un graphe valué, Sortie: plus court chemin
Début
1. Soit la matrice L (chaque colonne représente un sommet)
2. Initialement tous les sommets sont « non marqué »
3. Affecter la valeur 0 à L(Sdeb)et ∞ à tous les autres sommets
4. Tant Que Sfin n’est pas marqué faire
Marquer le sommet x non marqué de plus petit de L
Pour chaque sommet y non marqué voisin de x faire
L(y) = min { L(y), L(x) + M(x,y) }
FinPour
FinTantque
Fin
Tel que M est la matrice des longueurs (matrice d’adjacence) dont chaque élément
mi,j est définit comme suit :
A. Merabet – centre universitaire de Mila – 2020
32
Chapitre 4 : Problème du plus court chemin
Remarques :
▪ il ne s’applique qu’aux graphes à valuations positives
▪ il ne marche que pour trouver les plus courts chemins
▪ pour chaque sommet dans le chemin, sauvegarder toujours le sommet précèdent
Exemple :
M Sdeb a b c d Sfin
Sdeb 0 4 2 ∞ ∞ ∞
a 4 0 1 5 ∞ ∞
b 2 1 0 8 10 ∞
c ∞ 5 8 0 2 6
d ∞ ∞ 10 2 0 3
Sfin ∞ ∞ ∞ 6 3 0
Solution :
Itération 1: Marquer le sommet x non marqué de plus petit de L
L Sdeb a b c d Sfin
0 ∞ ∞ ∞ ∞ ∞
Pour chaque sommet y non marqué voisin de x faire
L(y) = min { L(y), L(x) + M(x,y) }
x = Sdeb donc, y 𝜖 { a, b} ➔ calculer : L(a), L(b)
L Sdeb a b c d Sfin
0 ∞ ∞ ∞ ∞ ∞ L(a) = min {∞, 0 + 4} = 4
L(b) = min {∞, 0 + 2} = 2
. 4 2 ∞ ∞ ∞
Itération 2 : Marquer le sommet x non marqué de plus petit de L
L Sdeb a b c d Sfin
0 ∞ ∞ ∞ ∞ ∞
. 4 2 ∞ ∞ ∞
x = b et y 𝜖 { a, c, d} ➔ calculer : L(a), L(c), L(d)
L(a) = min {4, 2+1}=3 ; L(c)= 2+8=10 ; L (d)=12
L Sdeb a b c d Sfin
0 ∞ ∞ ∞ ∞ ∞
. 4 2 ∞ ∞ ∞
. 3 2 10 12 ∞
Itération 3 Itération 4
L Sdeb a b c d Sfin L Sdeb a b c d Sfin
0 ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ ∞ ∞
. 4 2 ∞ ∞ ∞ . 4 2 ∞ ∞ ∞
. 3 . 10 12 ∞ . 3 . 8 12 ∞
L(c) = min {10, 3 + 5} = 8
A. Merabet – centre universitaire de Mila – 2020
33
Chapitre 4 : Problème du plus court chemin
Itération …
L Sdeb a b c d Sfin Sdeb a b c d Sfin
0 ∞ ∞ ∞ ∞ ∞ b Sdeb a c d
. 4 2 ∞ ∞ ∞
. 3 . 8 12 ∞
. . . 8 12 ∞
. . . . 10 14
. . . . . 13
Le plus court chemin est: Sdeb , b , a , c , d , Sfin
IV. Algorithme 9 : Algorithme de Bellman-Kalaba
Cas où les longueurs sont quelconques (positives ou négatives)
Algorithme 9 : permettant de trouver le plus court
chemin entre deux sommet Sdeb et Sfin
Entrée: G=(X;U)un graphe valué, Sortie: plus court chemin
Début
1. Initialisation
λ0(s1) = 0 pour tout si ≠ s 1 faire λ0(si) = ∞
FinPour
k = 1
2. à l’itération k
Faire λk(s1) = 0 et
pour tout si ≠ s1 Faire
𝜆𝑘 (𝑠𝑖 ) = 𝑀𝑖𝑛 ( 𝜆𝑘−1 (𝑠𝑖 ), 𝑀𝑖𝑛𝑠𝑗 ∈𝛤−1 (𝑠𝑖 ) (𝜆𝑘−1 (𝑠𝑗 ) + 𝑀(𝑠𝑗 , 𝑠𝑖 )) )
FinPour
3. Si k ≤ n − 1 aller en 2 avec k k + 1
Si λk(si) = λk−1(si) pour tout i alors FIN
Si k = n alors il existe un circuit absorbant
Fin
Remarques :
• Dans les graphes pondérés, le poids d'un circuit est la somme des poids des
arcs qu'il contient. Si ce poids est négatif, on parle de circuit absorbant.
si dans le graphe il existe un circuit de longueur négative, la recherche d’un
plus court chemin est sans objet. On peut utiliser le circuit une infinité de fois.
Exemple : Sdeb=x1 et Sfin=x5
A. Merabet – centre universitaire de Mila – 2020
34
Chapitre 4 : Problème du plus court chemin
M x1 x2 x3 x4 x5
x1 0 6 7 ∞ ∞
x2 ∞ 0 ∞ 2 1
x3 ∞ 2 0 2 ∞
x4 ∞ ∞ ∞ 0 3
x5 ∞ ∞ -2 ∞ 0
K λk(x1) λk(x2) λk(x3) λk(x4) λk(x5)
Initialisation 1 0 ∞ ∞ ∞ ∞
à l’itération 2 : λ2(x1) = 0 et
𝜆𝑘 (𝑠𝑖 ) = 𝑀𝑖𝑛 ( 𝜆𝑘−1 (𝑠𝑖 ), 𝑀𝑖𝑛𝑠𝑗 ∈𝛤−1 (𝑠𝑖 ) (𝜆𝑘−1 (𝑠𝑗 ) + 𝑀(𝑠𝑗 , 𝑠𝑖 )) )
• 𝜆2 (𝑥2 ) = 𝑀𝑖𝑛 ( 𝜆1 (𝑥2 ), 𝑀𝑖𝑛𝑠𝑗 ∈{𝑥1, 𝑥3} (𝜆1 (𝑠𝑗 ) + 𝑀(𝑠𝑗 , 𝑥2 )) )
= 𝑀𝑖𝑛 ( ∞ , 𝑀𝑖𝑛(𝜆1 (𝑥1 ) + 𝑀(𝑥1 , 𝑥2 ) , 𝜆1 (𝑥3 ) + 𝑀(𝑥3 , 𝑥2 ) ) )
= 𝑀𝑖𝑛 ( ∞ , 𝑀𝑖𝑛(0 + 6 , ∞ + 2 ) ) =6
• 𝜆2 (𝑥3 ) = 𝑀𝑖𝑛 ( 𝜆1 (𝑥3 ), 𝑀𝑖𝑛𝑠𝑗 ∈{𝑥1,𝑥5} (𝜆1 (𝑠𝑗 ) + 𝑀(𝑠𝑗 , 𝑥3 )) )
= 𝑀𝑖𝑛 ( ∞ , 𝑀𝑖𝑛(𝜆1 (𝑥1 ) + 𝑀(𝑥1 , 𝑥3 ), 𝜆1 (𝑥5 ) + 𝑀(𝑥5 , 𝑥3 ) ) )
= 𝑀𝑖𝑛 ( ∞ , 𝑀𝑖𝑛(0 + 7, ∞ − 2 ) ) =7
• 𝜆2 (𝑥4 ) = 𝑀𝑖𝑛 ( 𝜆1 (𝑥4 ), 𝑀𝑖𝑛𝑠𝑗 ∈{𝑥2,𝑥3} (𝜆1 (𝑠𝑗 ) + 𝑀(𝑠𝑗 , 𝑥4 )) )
= 𝑀𝑖𝑛 ( ∞ , 𝑀𝑖𝑛(𝜆1 (𝑥2 ) + 𝑀(𝑥2 , 𝑥4 ), 𝜆1 (𝑥3 ) + 𝑀(𝑥3 , 𝑥4 ) ) )
= 𝑀𝑖𝑛 ( ∞ , 𝑀𝑖𝑛(6 + 2, 7 + 2 ) ) =8
• 𝜆2 (𝑥5 ) = 𝑀𝑖𝑛 ( 𝜆1 (𝑥5 ), 𝑀𝑖𝑛𝑠𝑗 ∈{𝑥2,𝑥4} (𝜆1 (𝑠𝑗 ) + 𝑀(𝑠𝑗 , 𝑥5 )) )
= 𝑀𝑖𝑛 ( ∞ , 𝑀𝑖𝑛(𝜆1 (𝑥2 ) + 𝑀(𝑥2 , 𝑥5 ), 𝜆1 (𝑥4 ) + 𝑀(𝑥4 , 𝑥5 ) ) )
= 𝑀𝑖𝑛 ( ∞ , 𝑀𝑖𝑛(6 + 1, 8 + 3 ) ) =7
K λk(x1) λk(x2) λk(x3) λk(x4) λk(x5)
Initialisation 1 0 ∞ ∞ ∞ ∞
Itération 2 2 0 6 7 7 8
Le résultat final est :
K λk(x1) λk(x2) λk(x3) λk(x4) λk(x5)
Initialisation 1 0 ∞ ∞ ∞ ∞
Itération 2 2 0 6 7 8 7
Itération 3 3 0 6 5 7 7
Itération 4 4 0 6 5 7 7
A. Merabet – centre universitaire de Mila – 2020
