Plus court chemin et Algorithme de Dijkstra

Objectif : Etant donné 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 un graphe valué (valeurs non-négatives) sur les arcs/arêtes et un sommet initial 𝑠𝑠,
déterminer la distance du plus court chemin entre 𝑠𝑠 et tout sommet atteignable.

Applications : câblage dans une centrale nucléaire, routages dans l’internet…

 Opération triangulaire et calcul du plus court chemin
j

𝑑𝑑𝑖𝑖𝑖𝑖 Etant donné une matrice [𝑑𝑑𝑗𝑗𝑗𝑗] de distance nxn l’opération triangulaire for sommet k est :
𝑑𝑑𝑗𝑗𝑗𝑗
𝑑𝑑𝑖𝑖𝑖𝑖 = min {𝑑𝑑𝑖𝑖𝑖𝑖, 𝑑𝑑𝑖𝑖𝑖𝑖 + 𝑑𝑑𝑗𝑗𝑗𝑗 }, pour tout i, k = 1,...,n et i,k =/= j
i k
𝑑𝑑𝑖𝑖𝑖𝑖
X1 𝑐𝑐𝑥𝑥1𝐵𝐵 Le plus court chemin de A à B: r(B)
x2 𝑐𝑐𝑥𝑥2𝐵𝐵 B
A r(B)=min{ r(xi) + 𝑐𝑐𝑥𝑥𝑥𝑥𝑥𝑥 : i=1,…,k }
𝑐𝑐𝑥𝑥𝑘𝑘𝑘𝑘
Xk Rm : chaque r(xi) + 𝑐𝑐𝑥𝑥𝑥𝑥𝑥𝑥est un majorant de r(B) (borne sup)

V-W 𝜌𝜌 𝑦𝑦 =10
10 y
W
𝑐𝑐𝑥𝑥𝑥𝑥 = 2
y s x
y 𝜌𝜌 𝑥𝑥 =5
s x y
y
 Algorithme de Dijkstra

Pour tout 𝑢𝑢, 𝑣𝑣 ∈ 𝑉𝑉, on définit 𝑐𝑐𝑢𝑢𝑢𝑢 ≥ 0 si 𝑢𝑢, 𝑣𝑣 ∈ 𝐸𝐸; 𝑐𝑐𝑢𝑢𝑢𝑢 = ∞ si 𝑢𝑢, 𝑣𝑣 ∉ 𝐸𝐸.

𝑊𝑊 = {𝑥𝑥 ∈ 𝑉𝑉 | le plus court chemin de 𝑠𝑠 à 𝑥𝑥 est connu}

Un vecteur 𝜌𝜌[𝑥𝑥] de taille |V| où 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 𝑥𝑥 ∈ 𝑉𝑉, 𝑡𝑡𝑡𝑡
𝑠𝑠𝑠𝑠 𝑥𝑥 ∈ 𝑊𝑊, 𝜌𝜌 𝑥𝑥 = la distance du plus court chemin de 𝑠𝑠 à 𝑥𝑥.
𝑠𝑠𝑠𝑠 𝑥𝑥 ∉ 𝑊𝑊, 𝜌𝜌 𝑥𝑥 = le meilleur majorant jusqu′ à présent de la distance du plus court chemin de 𝑠𝑠 à 𝑥𝑥
(𝐞𝐞𝐞𝐞 𝐩𝐩𝐩𝐩𝐩𝐩𝐩𝐩𝐩𝐩𝐩𝐩𝐩𝐩 𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮𝐮 𝐩𝐩𝐩𝐩𝐩𝐩 𝐥𝐥𝐥𝐥𝐥𝐥 𝐬𝐬𝐬𝐬𝐬𝐬𝐬𝐬𝐬𝐬𝐬𝐬𝐬𝐬 𝑑𝑑𝑑𝑑 𝑊𝑊).

L’idée de l’algorithme :
𝑐𝑐𝑠𝑠𝑠𝑠 ≥ 0, si 𝑠𝑠, 𝑦𝑦 ∈ 𝐸𝐸
Initialisation: 𝑊𝑊 = {𝑠𝑠}, 𝜌𝜌 𝑠𝑠 = 0; pour tout 𝑦𝑦 ∈ 𝑉𝑉 ∖ 𝑠𝑠 , on définit 𝜌𝜌 𝑦𝑦 = �
∞, sinon, i. e. , 𝑠𝑠, 𝑦𝑦 ∉ 𝐸𝐸

Extension de 𝑊𝑊 (itération par itération): étendre 𝑊𝑊 par un sommet 𝑥𝑥 ∈ 𝑉𝑉 ∖ 𝑊𝑊 𝑥𝑥 ∉ 𝑊𝑊 tq 𝜌𝜌 𝑥𝑥 = min{𝜌𝜌 𝑦𝑦 | 𝑦𝑦 ∈ 𝑉𝑉 ∖ 𝑊𝑊}

𝜌𝜌 𝑥𝑥 + 𝑐𝑐𝑥𝑥𝑥𝑥, 𝑠𝑠𝑠𝑠 𝜌𝜌 𝑥𝑥 + 𝑐𝑐𝑥𝑥𝑦𝑦 < 𝜌𝜌 𝑦𝑦

Mis à jour du vecteur 𝜌𝜌: pour tout successeur 𝑦𝑦 de 𝑥𝑥 et 𝑦𝑦 ∉ 𝑊𝑊, 𝜌𝜌 𝑦𝑦 = �
𝜌𝜌 𝑦𝑦 , sinon
 Plus court chemin et Algorithme de Dijkstra
Algorithme de Dijikstra
Input : Graphe orienté 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 avec valuations 𝑐𝑐𝑢𝑢𝑢𝑢 ≥ 0 sur les arcs et un sommet 𝑠𝑠 ∈ 𝑉𝑉
Output : Vecteur 𝜌𝜌 de taille |V| : pour tout 𝑥𝑥 ∈ 𝑉𝑉, 𝜌𝜌 𝑥𝑥 = la distance du plus court chemin de s à 𝑥𝑥 atteignable
begin
𝑊𝑊 ← 𝑠𝑠 ; 𝜌𝜌 𝑠𝑠 ← 0;
𝒇𝒇𝒇𝒇𝒇𝒇 tout 𝑦𝑦 ∈ 𝑉𝑉 ∖ {𝑠𝑠} 𝒅𝒅𝒅𝒅 𝜌𝜌 𝑦𝑦 ← 𝑐𝑐𝑠𝑠𝑠𝑠
𝒘𝒘𝒘𝒘𝒘𝒘𝒘𝒘𝒘𝒘 𝑊𝑊 ≠ 𝑉𝑉 𝒅𝒅𝒅𝒅
begin
Chercher le plus petit 𝜌𝜌 𝑥𝑥 = min 𝜌𝜌 𝑦𝑦 𝑦𝑦 ∉ 𝑊𝑊};
𝑊𝑊 ← 𝑊𝑊 ∪ 𝑥𝑥 ;
𝒇𝒇𝒇𝒇𝒇𝒇 tout 𝑦𝑦 ∈ 𝑉𝑉 ∖ W 𝒅𝒅𝒅𝒅
𝜌𝜌 𝑦𝑦 ← min{𝜌𝜌 𝑦𝑦 , 𝜌𝜌 𝑥𝑥 + 𝑐𝑐𝑥𝑥𝑦𝑦}
end
end
Complexité en temps
1) Initialisation du vecteur 𝜌𝜌: 𝑂𝑂(|V |)
2) Boucle principale : |V | itérations et chaque itération est bornée par 𝑂𝑂 |V | , donc 𝑂𝑂(|V |2 ) au total.
Rm:
L’algorithme ne donne pas les chemins, mais la distance de chaque plus court chemin.
 Plus court chemin et Algorithme de Dijkstra

Ex: Dérouler l’algorithme de Dijkstra en donnant

l’état de 𝑊𝑊 et 𝜌𝜌 itération par iteration;
Indiquer les valeurs mises à jour de 𝜌𝜌.
 Distances minimales entre chaque paire de sommets et algorithme de Floyd-Warshall
u

𝑑𝑑𝑣𝑣𝑣𝑣 Etant donné une matrice [𝑑𝑑] de distance nxn l’opération triangulaire pour sommet w est :
𝑑𝑑𝑢𝑢𝑢𝑢
𝑑𝑑𝑣𝑣𝑣𝑣 = min {𝑑𝑑𝑣𝑣𝑣𝑣, 𝑑𝑑𝑣𝑣𝑣𝑣 + 𝑑𝑑𝑢𝑢𝑢𝑢 }, pour tout v, w = 1,...,n et v,w =/= u
v w
𝑑𝑑𝑣𝑣𝑣𝑣

L’idée: on considère chaque sommet u tour à tour comme un pivot, on examine chaque paire de sommets v et w
ayant u comme somme intermédiaire.

Si d(v,u) + d(u,w) < d(v,w), alors d(v,w) = d(v,u) + d(u,w)

Hypothèses :

1. Les sommets sont numérotés de 1 à n

2. Le graphe est représenté par sa matrice de distance A
3. On utilise une matrice d[nxn] pour représenter la distance minimale entre chaque paire de sommets
 Algorithme de Floyd-Warshall

Input: graphe représenté par sa matrice A d’adjacence

Output: matrice d de distance minimale entre chaque paire de sommets

Var: u, v, w: Entiers
Début
pour v = 1 à n faire
pour w = 1 à n faire
d(v,w) = A(v,w) /* A est la matrice d’adjacence
pour u = 1 à n faire /* u est le pivot
pour v = 1 à n faire
pour w = 1 à n faire
si d(v,u) + d(u,w) < d(v,w)
alors d(v,w) = d(v,u) + d(u,w)

Rm:

1. Complexité O(𝑛𝑛3 )
2. Applicable aux graphes orientés et non-orientés
Example

Pas de changement avec pivot 4 Pivot 5

 Justification de de l’algorithme de Floyd-Warshall

Une fois fini, nous avons, pour tout v,w, d(v,w) = la longueur du plus court chemin entre v et w.

Déf : (k-chemin) : un k-chemin de v à w est un chemin dont les sommets intermédiaires ont un no ≤ k.

Ex:
• 1-2-3-4 : 3-chemin (mais aussi 4-chemin, 5-chemin…)
• 0-chemin est un sommet ou un arc
• Un n-chemin est un chemin quelconque (n = le nombre des sommets du graphe)

Démonstration par récurrence

Assertion S(k) : juste après l’itération u = k, d(v,w) = la longueur du plus court k-chemin de v à w.

La base : si k = 0, S(0) est vrai car d(v,w) = A(v,w)

Récurrence : Supposons S(k), on cherche à démontrer S(k+1), i.e.,

après itérations u=k+1, d(v,w) = la longueur du plus court (k+1)-chemin de v à w.
 Justification de de l’algorithme de Floyd-Warshall (suite)
Sout C un plus court (k+1)-chemin de v à w, deux cas sont possibles selon si C passe ou non par le sommet k+1.

1) C ne passe pas par le sommet k+1, l’itération courante (k+1) n’a aucune influence sur d(v,w) qui est égale à
la longueur du plus court k-chemin, donc (k+1)-chemin. Done.

2) C passe par k+1, C est donc composé d’un k-chemin A et d’un k-chemin B : v - - - - - - (k+1) - - - - - - - w

D’après l’hypothèse S(k),

- d(v,k+1) = la longueur du plus court k-chemin de v à k+1
- d(k+1,w) = la longueur du plus court k-chemin de k+1 à w.

Le test d(v,k+1) + d(k+1,w) < d(v,w) réussit (car C est le plus court (k+1)-chemin de v à w),

Selon l’algorithme, l’affectation d(v,w) = d(v,k+1) + d(k+1,w) est alors effectuée.

Donc d(v,w) = la longueur du plus court k-chemin de v à w après l’itération (k+1).

Puisque un k-chemin est aussi un (k+1) chemin, on obtient le résultat.

Pour un graphe de n sommets, on pose k=n.

 Fermeture transitive et réflexive de G

L’algorithme est fondé sur la récurrence suivante :

1) exchemin(x,y) = arc(x,y)
2) exchemin(x,y) = exchemin(x,i) ET arc(i,y)

On replace la matrice de distance par une matrice d[nxn] booléenne, et on replace l’opération triangulaire par
une opération booléenne.
Exemple d’application (compilateur)
Var: u, v, w: booléenne Un graphe de dépendance est un graphe où
Début les sommets sont des variables et un arc entre
la variable x et la variable y indique que le calcul de a
pour v = 1 à n faire
nécessite le calcul de b.
pour w = 1 à n faire
d(v,w) = vrai ou faux selon si (v,w) ∈ 𝐸𝐸) La fermeture transitive de ce graphe donne toutes les
pour u = 1 à n faire variables nécessaires directement ou indirectement
pour v = 1 à n faire au calcul de a.
pour w = 1 à n faire
si NOT d(v,w) Cette information permet de minimiser la quantité
alors d(v,w) = d(v,u) ET d(u,w) de calculs à effectuer en machine pour l'exécution
du programme.
 Fermeture transitive et réflexive

Dérouler l’algorithme sur le graphe G suivant

G G*