Introduction et définitions

Plus court chemin dans un graphe non valué

Plus court chemin dans un graphe valué
Algorithme de Dijkstra

CHAPITRE III :
RECHERCHE DU PLUS COURT CHEMIN

Mohamed Khairallah KHOUJA

ISET MAHDIA

2019/2020

1 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Plus court chemin dans un graphe non valué
Plus court chemin dans un graphe valué
Algorithme de Dijkstra

PLAN

1 Introduction et définitions
2 Plus court chemin dans un graphe non valué
Principe de sous-optimalité
Algorithme de recherche
Algorithme de recherche en largeur BFS
3 Plus court chemin dans un graphe valué
4 Algorithme de Dijkstra
Propriété de la distance partielle
Algorithme de recherche des plus courts chemins
Propriété de mise à jour des distances partielles
Algorithme de Dijkstra avec file de priorité (BFS)

2 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Plus court chemin dans un graphe non valué
Plus court chemin dans un graphe valué
Algorithme de Dijkstra

Introduction

Nous aimerions disposer d’une méthode capable, pour tout

graphe et pour toute paire de sommets s et t, de déterminer le
plus court chemin entre eux. Résoudre ce problème va donc
consister à proposer un algorithme, aussi rapide que possible.
Dans un premier temps, nous allons calculer la longueur de
tous les plus courts chemins dans un graphe non valué :
nombre d’arêtes minimum.
Ensuite, nous allons généraliser dans le cas de graphes
valués, où chaque arête e est associée à une valeur, appelée
souvent son poids, c(e) : le chemin de poids minimum, celui
dont la somme des poids des arêtes est le plus faible possible.
L’algorithme de Dijkstra est l’un de ceux qui convient le
mieux.

3 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Plus court chemin dans un graphe non valué
Plus court chemin dans un graphe valué
Algorithme de Dijkstra

Réseau

Définition
Un réseau est un graphe G = (X;U) auquel on associe une
fonction d : U → < qui à chaque arc fait correspondre sa
longueur.
On note R = (X ; U; d) un tel réseau.

4 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Plus court chemin dans un graphe non valué
Plus court chemin dans un graphe valué
Algorithme de Dijkstra

Longueur

Définition
La longueur d’un chemin (d’une chaı̂ne, d’un circuit ou d’un
cycle) est la somme des longueurs de chaque arc qui le
compose.
Par convention, un chemin (une chaı̂ne, un circuit ou un
cycle) qui ne contient pas d’arc est de longueur nulle.

5 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Principe de sous-optimalité
Plus court chemin dans un graphe non valué
Algorithme de recherche
Plus court chemin dans un graphe valué
Algorithme de recherche en largeur BFS
Algorithme de Dijkstra

PLAN

1 Introduction et définitions
2 Plus court chemin dans un graphe non valué
Principe de sous-optimalité
Algorithme de recherche
Algorithme de recherche en largeur BFS
3 Plus court chemin dans un graphe valué
4 Algorithme de Dijkstra
Propriété de la distance partielle
Algorithme de recherche des plus courts chemins
Propriété de mise à jour des distances partielles
Algorithme de Dijkstra avec file de priorité (BFS)

6 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Principe de sous-optimalité
Plus court chemin dans un graphe non valué
Algorithme de recherche
Plus court chemin dans un graphe valué
Algorithme de recherche en largeur BFS
Algorithme de Dijkstra

Principe de sous-optimalité
Un plus court chemin entre 2 sommets est élémentaire.
Les plus courts chemins vérifient le principe de
sous-optimalité : si p = (s, ..., t) est un plus court chemin
entre s et t, alors pour tout sommet x sur le chemin, le
sous-chemin de p jusqu’à x, (s, ..., x), est un plus court
chemin de s à x.

7 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Principe de sous-optimalité
Plus court chemin dans un graphe non valué
Algorithme de recherche
Plus court chemin dans un graphe valué
Algorithme de recherche en largeur BFS
Algorithme de Dijkstra

Algorithme de recherche
Il s’agit de partir de s (distance 0), et de visiter successivement ses
voisins (distance 1), puis les voisins de ses voisins non encore
visités (distance 2), les voisins des voisins des voisins non encore
visités, et ainsi de suite.

8 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Principe de sous-optimalité
Plus court chemin dans un graphe non valué
Algorithme de recherche
Plus court chemin dans un graphe valué
Algorithme de recherche en largeur BFS
Algorithme de Dijkstra

Algorithme de recherche

Entrées: G = (X;U) un graphe, s un sommet.

Procédure Recherche
Initialiser tous les sommets à non marqué ;
Marquer s ;
Tant que (il existe un sommet non marqué adjacent à un som-
met marqué ) faire
Sélectionner un sommet y non marqué adjacent à un som-
met marqué;
Marquer y;
Fait

9 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Principe de sous-optimalité
Plus court chemin dans un graphe non valué
Algorithme de recherche
Plus court chemin dans un graphe valué
Algorithme de recherche en largeur BFS
Algorithme de Dijkstra

Algorithme de recherche

Définition
La recherche en profondeur DFS (Depth First Search) :
Dans l’exploration, l’algorithme cherche à aller très vite
”profondément” dans le graphe, en s’éloignant du sommet s
de départ. La recherche sélectionne à chaque étape un
sommet voisin du sommet marqué à l’étape précédente.
La recherche en largeur BFS (Breath First Search) :
Dans l’exploration l’algorithme cherche au contraire à épuiser
la liste des sommets proches de s avant de poursuivre
l’exploration du graphe.

10 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Principe de sous-optimalité
Plus court chemin dans un graphe non valué
Algorithme de recherche
Plus court chemin dans un graphe valué
Algorithme de recherche en largeur BFS
Algorithme de Dijkstra

Algorithme de recherche
Le résultat de chacune des recherche est représenté par son arbre
de recherche : une arête existe entre deux sommets x et y si la
visite (marquage) de y se fait à partir de x.

11 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Principe de sous-optimalité
Plus court chemin dans un graphe non valué
Algorithme de recherche
Plus court chemin dans un graphe valué
Algorithme de recherche en largeur BFS
Algorithme de Dijkstra

Algorithme de recherche
Exemple
En profondeur: Les sommets En largeur : Les sommets sont
sont visités depuis s dans l’ordre visités depuis s dans l’ordre A,
A, D, E, B, F, I, G, H, C B, C, D, E, I, F, G, H

12 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Principe de sous-optimalité
Plus court chemin dans un graphe non valué
Algorithme de recherche
Plus court chemin dans un graphe valué
Algorithme de recherche en largeur BFS
Algorithme de Dijkstra

Plus court chemin dans un graphe non valué

La recherche en largeur semble bien correspondre à l’ordre de
visite du graphe que nous cherchons pour résoudre le
problème des plus courts chemins.
Pour cela, nous maintenons dans une structure de données M
l’ensemble des sommets marqués dont nous n’avons pas
encore traité les voisins.
Une étape de la recherche consiste à sélectionner l’un de ces
sommets (en le retirant de M), à marquer tous ses voisins
(non encore marqués) et à les ajouter à M.
La structure de données M doit donc posséder 2 actions :
l’ajout d’un sommet x (noté Mx), et le retrait du sommet en
tête de la structure (noté xM).
La fonction pred() permet de garder le prédécesseur ceci afin
de tracer plus tard le plus court chemin à l’envers de
n’importe quel un sommet au sommet source s
13 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN
 Introduction et définitions
Principe de sous-optimalité
Plus court chemin dans un graphe non valué
Algorithme de recherche
Plus court chemin dans un graphe valué
Algorithme de recherche en largeur BFS
Algorithme de Dijkstra

Algorithme de recherche

Entrées: G = (X;U) un graphe, s un sommet, M : structure

de données ordonnée
Procédure Recherche
Initialiser tous les sommets à non marqué ; Marquer s ;
M←s
Tant que (M n’est pas vide) faire
x ← M; //Retirer le ”premier” sommet de l’ensemble M
Pour chaque voisin y non marqué de x faire
Marquer y;
Pred(y) ← x ; // x est le prédécesseur de y
M ← y ; // Ajouter y à l’ensemble M
Fin Pour
Fait
14 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN
 Introduction et définitions
Principe de sous-optimalité
Plus court chemin dans un graphe non valué
Algorithme de recherche
Plus court chemin dans un graphe valué
Algorithme de recherche en largeur BFS
Algorithme de Dijkstra

Plus court chemin dans un graphe non valué

La Recherche en Profondeur correspond à prendre pour M

une structure de PILE, c’est à dire une liste LIFO
LastIn/FirstOut (dernier entré/premier sorti)
La Recherche en Largeur correspond à prendre pour M une
structure de FILE, c’est à dire une liste FIFO FirstIn/FirstOut
(premier entré/premier sorti)

15 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Principe de sous-optimalité
Plus court chemin dans un graphe non valué
Algorithme de recherche
Plus court chemin dans un graphe valué
Algorithme de recherche en largeur BFS
Algorithme de Dijkstra

Algorithme de recherche en largeur BFS

Entrées: G = (X;U) un graphe, s un sommet, F : FILE

Procédure Recherche BFS
Initialiser tous les sommets à non marqué ; Marquer s ;
L(s) ← 0 ; F ← s; // L label
Tant que (F n’est pas vide) faire
x ← F; //Retirer le premier sommet de la file
Pour chaque voisin y non marqué de x faire
Marquer y;
Pred(y) ← x ; // x est le prédécesseur de y
L(y) ← L(x)+1 ;
F ← y ; // Ajouter y à la fin de la file
Fin Pour
Fait
16 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN
 Introduction et définitions
Plus court chemin dans un graphe non valué
Plus court chemin dans un graphe valué
Algorithme de Dijkstra

PLAN

1 Introduction et définitions
2 Plus court chemin dans un graphe non valué
Principe de sous-optimalité
Algorithme de recherche
Algorithme de recherche en largeur BFS
3 Plus court chemin dans un graphe valué
4 Algorithme de Dijkstra
Propriété de la distance partielle
Algorithme de recherche des plus courts chemins
Propriété de mise à jour des distances partielles
Algorithme de Dijkstra avec file de priorité (BFS)

17 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Plus court chemin dans un graphe non valué
Plus court chemin dans un graphe valué
Algorithme de Dijkstra

Plus court chemin dans un graphe valué

Dans un graphe valué, le poids c(p) d’un chemin p est la

somme des poids des arêtes le long du chemin.
Dans ce qui suit nous appellerons le poids d’un chemin sa
longueur. Le plus court chemin entre 2 sommets s et t est
alors défini comme le chemin de plus faible poids reliant s et t.

18 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Plus court chemin dans un graphe non valué
Plus court chemin dans un graphe valué
Algorithme de Dijkstra

Principe de sous-optimalité dans un graphe valué

Nous allons nous intéresser dans un premier temps à des

graphes sur lesquels toutes les valuations des arêtes sont
positives.
Sous cette condition, les propriétés que nous avons données
pour le plus court chemin en nombre d’arêtes restent vérifiées
pour le chemin de plus faible poids.
Si D(y) est la longueur du plus court chemin d’un sommet y
à s, le principe de sous-optimalité se traduit localement par
les égalités
D(y ) = 0 si y = s
D(y ) = min{D(x) + c(x, y ) | x voisin de y } sinon

19 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions
Plus court chemin dans un graphe non valué
Plus court chemin dans un graphe valué
Algorithme de Dijkstra

Algorithmes

Pour trouver les plus court chemins dans un graphe valué, nous
allons voir 2 algorithmes très différents :
Algorithme de Dijkstra : Cet algorithme est une adaptation
de l’algorithme de recherche pour calculer les plus court
chemin d’un sommet s à tous les autres sommets du graphe.
Algorithme de Bellman : Cet algorithme est plus complexe,
plus long en temps, mais plus puissant : il détermine la
distance de tous les plus courts chemins entre toutes les paires
de sommets d’un graphe, pouvant avoir des valuations
négatives ou positives de ses arêtes. Son principe repose sur
un paradigme algorithmique très général : la programmation
dynamique.

20 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions Propriété de la distance partielle
Plus court chemin dans un graphe non valué Algorithme de recherche des plus courts chemins
Plus court chemin dans un graphe valué Propriété de mise à jour des distances partielles
Algorithme de Dijkstra Algorithme de Dijkstra avec file de priorité (BFS)

PLAN

1 Introduction et définitions
2 Plus court chemin dans un graphe non valué
Principe de sous-optimalité
Algorithme de recherche
Algorithme de recherche en largeur BFS
3 Plus court chemin dans un graphe valué
4 Algorithme de Dijkstra
Propriété de la distance partielle
Algorithme de recherche des plus courts chemins
Propriété de mise à jour des distances partielles
Algorithme de Dijkstra avec file de priorité (BFS)

21 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions Propriété de la distance partielle
Plus court chemin dans un graphe non valué Algorithme de recherche des plus courts chemins
Plus court chemin dans un graphe valué Propriété de mise à jour des distances partielles
Algorithme de Dijkstra Algorithme de Dijkstra avec file de priorité (BFS)

Propriété de la distance partielle

Imaginons que nous ayons déjà marqué avec notre algorithme

de recherche un ensemble S de sommets, pour lesquels nous
avons déterminé leur plus court chemin à s.
Un ”bon” ordre d’exploration revient à sélectionner le
prochain sommet y à marquer de telle sorte que nous
puissions calculer D(y ) uniquement à partir des distances
D(x) des sommets x marqués. Une telle exploration est
possible grâce à la propriété suivante :

22 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions Propriété de la distance partielle
Plus court chemin dans un graphe non valué Algorithme de recherche des plus courts chemins
Plus court chemin dans un graphe valué Propriété de mise à jour des distances partielles
Algorithme de Dijkstra Algorithme de Dijkstra avec file de priorité (BFS)

Propriété de la distance partielle

Considérons un ensemble S de sommets incluant la source s.

Pour tout sommet z en dehors de S, nous définissons sa
distance partielle à s par :
DP(S, z) = min{D(x) + c(x, z) | x ∈ S et x voisin de z }
Alors si y est un sommet avec la plus petite distance partielle,
sa distance partielle est égale à sa distance à s :
DP(S, y ) = D(y )
La distance partielle correspond à la longueur du plus court
chemin de s à z qui n’emprunte que des sommets de S, à
l’exception du dernier sommet z. C’est donc le plus court
chemin dans le sous-graphe induit par S ∪ z. Par convention
la distance partielle d’un sommet est infinie si il n’est adjacent
à aucun sommet de S.

23 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions Propriété de la distance partielle
Plus court chemin dans un graphe non valué Algorithme de recherche des plus courts chemins
Plus court chemin dans un graphe valué Propriété de mise à jour des distances partielles
Algorithme de Dijkstra Algorithme de Dijkstra avec file de priorité (BFS)

Exemple

Exemple

24 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions Propriété de la distance partielle
Plus court chemin dans un graphe non valué Algorithme de recherche des plus courts chemins
Plus court chemin dans un graphe valué Propriété de mise à jour des distances partielles
Algorithme de Dijkstra Algorithme de Dijkstra avec file de priorité (BFS)

Exemple

Exemple
Le sommet d joue le rôle de la source s. L’ensemble S des
sommets marqués est {a, d, e}.
Les distances sont indiquées à coté de chaque sommet, en
grisé pour les distances partielles des sommets non marqués,
en jaune pour les plus courtes distances des sommets marqués.
La distance partielle de f est infinie, sa distance à d est
D(f ) = 10 (d-e-h-g-f)
La distance partielle de g est DP(S, g ) = 9, sa distance est
D(g ) = 7 (d-e-h-g)
Par contre pour h, le sommet de plus petite distance partielle,
on a bien l’égalité DP(h) = D(h) = 5

25 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions Propriété de la distance partielle
Plus court chemin dans un graphe non valué Algorithme de recherche des plus courts chemins
Plus court chemin dans un graphe valué Propriété de mise à jour des distances partielles
Algorithme de Dijkstra Algorithme de Dijkstra avec file de priorité (BFS)

Algorithme de recherche des plus courts chemins

L’idée est de marquer les nœuds du graphe en sélectionnant à

chaque étape le sommet non marqué de plus petite distance
partielle.
Un label est maintenu pour chaque sommet : à la fin de
l’algorithme ce label est égal à sa distance à s.
On peut remarquer que l’algorithme ci-après suit le schéma de
notre algorithme de recherche : à chaque étape le sommet y
sélectionné est en effet adjacent à un sommet déjà marqué,
sinon son label serait infini.

26 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions Propriété de la distance partielle
Plus court chemin dans un graphe non valué Algorithme de recherche des plus courts chemins
Plus court chemin dans un graphe valué Propriété de mise à jour des distances partielles
Algorithme de Dijkstra Algorithme de Dijkstra avec file de priorité (BFS)

Algorithme de recherche des plus courts chemins

Entrées: G = (X;U) un graphe avec une valuation positive c

des arêtes, s un sommet;
Initialiser tous les sommets à non marqué ; Marquer s ;
L(s) ← 0 ; // Initialise le label de s à 0
Tant que (il existe un sommet non marqué ) faire
Pour chaque sommet y non marqué faire
Calculer L(y ) ← min{L(x) + c(x, y ) | x voisin
marqué de y };
Fin Pour
Choisir le sommet y non marqué de plus petit label L;
Marquer y;
Fait

27 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions Propriété de la distance partielle
Plus court chemin dans un graphe non valué Algorithme de recherche des plus courts chemins
Plus court chemin dans un graphe valué Propriété de mise à jour des distances partielles
Algorithme de Dijkstra Algorithme de Dijkstra avec file de priorité (BFS)

Propriété de mise à jour des distances partielles

Dans l’algorithme de Dijkstra les opérations les plus coûteuses

sont le calcul à chaque étape des distances partielles.
Cependant une bonne partie de ces opérations sont inutiles :
lors du marquage d’un sommet x, seuls les voisins de x
peuvent éventuellement voire leur distance partielle modifiée.
Considérons un ensemble S de sommets incluant la source s,
et un sommet y . Pour tout sommet z en dehors de S{y } :
DP(S ∪ y , z) = min{DP(S, z), D(y ) + c(y , z)} Si (y , z) ∈ E
DP(S ∪ y , z) = DP(S, z) Sinon.

28 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions Propriété de la distance partielle
Plus court chemin dans un graphe non valué Algorithme de recherche des plus courts chemins
Plus court chemin dans un graphe valué Propriété de mise à jour des distances partielles
Algorithme de Dijkstra Algorithme de Dijkstra avec file de priorité (BFS)

Algorithme de Dijkstra avec file de priorité (BFS)

L’algorithme de Dijkstra utilise cette propriété pour ne mettre

à jour à chaque étape que les distances partielles des sommets
adjacents au sommet qui vient d’être marqué.
Initialement toutes les labels, représentant les distances, sont
initialisés à + ∝, sauf celui de la source s mis à 0. Chaque
étape de l’algorithme comporte ensuite 2 phases :
Une phase de sélection : Comme pour l’algorithme de
recherche des plus courts chemins, le sommet y non marqué de
plus petit label est sélectionné.
Une phase de mise à jour les labels des sommets z non
marqués adjacents au sommet y qui vient d’être sélectionné
sont mis à jour : L(z) = min{L(z), L(y ) + c(y , z)}

29 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions Propriété de la distance partielle
Plus court chemin dans un graphe non valué Algorithme de recherche des plus courts chemins
Plus court chemin dans un graphe valué Propriété de mise à jour des distances partielles
Algorithme de Dijkstra Algorithme de Dijkstra avec file de priorité (BFS)

Algorithme de Dijkstra avec file de priorité (BFS)

Entrées: G = (X;U) un graphe avec une valuation positive c

des arêtes, s un sommet;
F : FILE de priorité trié par ordre croissant de poids;

Initialiser tous les sommets à non marqué ;

Initialiser tous les labels L à + ∝ ;
L(s) ← 0 ;

30 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN

 Introduction et définitions Propriété de la distance partielle
Plus court chemin dans un graphe non valué Algorithme de recherche des plus courts chemins
Plus court chemin dans un graphe valué Propriété de mise à jour des distances partielles
Algorithme de Dijkstra Algorithme de Dijkstra avec file de priorité (BFS)

Algorithme de Dijkstra avec file de priorité (BFS)

Tant que (il existe un sommet non marqué ) faire

// Sélection du plus ’proche’ sommet non marqué y de
plus petit label L
y ← F ; // Retirer le premier sommet de la file
Marquer y ;
// Mise à jour des labels de ses voisins non marqués
Pour chaque sommet z non marqué voisin de y faire
L(z) ← min{L(z), L(y ) + c(y , z)}
Pred(y ) ← z // x est le prédécesseur de y
F ← z // Ajouter z à la file de priorité à trier par
ordre croissant des poids
Fin Pour
Fait
31 Mohamed Khairallah KHOUJA CHAPITRE III : RECHERCHE DU PLUS COURT CHEMIN