ALGORITHME DE DIJKSTRA
Prof: Ahmed EL HAMMOUDI
Chapitre : Les graphes
Les structures dont on aura besoin
P = le graphe couvert = liste des sommets déjà visités.
Q = le graphe restant = liste des sommets à visiter.
d = Liste des distances de chaque sommet t.q d[i]=la distance
entre le sommet de départ et le sommet i.
pred = Liste des prédesseurs des sommets : pred[i]=j signifie
que dans le chemin optimal entre le sommet de départ et i,
j est le sommet qui préceède i.
Étape initiale
A(0)
P=[ ] B(00) C(00)
Q=[A] E(00)
d= 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
A B C D E F G H I J
pred=
A B C D E F G H I J
Étape 1
P=[A]
Q=[B,C,E]
d= 0 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞
A B C D E F G H I J
pred= A A A
A B C D E F G H I J
Étape 2
P=[A,B]
Q=[C,E,F]
d= 0 85 217 ∞ 173 165 ∞ ∞ ∞ ∞
A B C D E F G H I J
pred= A A A B
A B C D E F G H I J
Étape 3
P=[A,B,F]
Q=[C,E,I]
d= 0 85 217 ∞ 173 165 ∞ ∞ 415 ∞
A B C D E F G H I J
pred= A A A B F
A B C D E F G H I J
Étape 4
P=[A,B,F,E]
Q=[C,I,J]
d= 0 85 217 ∞ 173 165 ∞ ∞ 415 675
A B C D E F G H I J
pred= A A A B F E
A B C D E F G H I J
Étape 5
P=[A,B,F,E,C]
Q=[I,J,G,H]
d= 0 85 217 ∞ 173 165 403 320 415 675
A B C D E F G H I J
pred= A A A B C C F E
A B C D E F G H I J
Étape 6
P=[A,B,F,E,C,H]
Q=[I,J,G,D] 675
d= 0 85 217 503 173 165 403 320 415 487
A B C D E F G H I J
pred= A A H A B C C F H E
A B C D E F G H I J
Étape 7
P=[A,B,F,E,C,H,G]
Q=[I,J,D]
d= 0 85 217 503 173 165 403 320 415 487
A B C D E F G H I J
pred= A A H A B C C F H
A B C D E F G H I J
Étape 8
P=[A,B,F,E,C,H,G,I] Ne change pas
415+84>487
Q=[J,D]
d= 0 85 217 503 173 165 403 320 415 487
A B C D E F G H I J
pred= A A H A B C C F H
A B C D E F G H I J
Étape 9
P=[A,B,F,E,C,H,G,I,J] Fin de la
recherche
Q=[D]
d= 0 85 217 503 173 165 403 320 415 487
A B C D E F G H I J
pred= A A H A B C C F H
A B C D E F G H I J
Chemin=[A,C,H,J]
Les fonctions à définir (G=(S,A))
voisins(G, poids,i) qui renvoie la liste d’adjacence
du sommet i sous la forme de :
[(j,p)/ j voisin de i et p = le poids du lien (i,j)].
trouveMin(Q, d) qui renvoie et retire de Q (la file de
sommets) le sommet i appartenant à Q qui a la plus
petite distance ; Càd d[i]=min([d[j]/j c Q]).
dijkstra(G, poids, Sdeb, Sfin) qui renvoie le chemin
le plus cours du sommet Sdeb vers le sommet Sfin.
Les fonctions à définir (M = Matrice d'adjacence)
voisins(i,M) qui renvoie la liste d’adjacence du
sommet i sous la forme de :
[(j,p)/ j voisin de i et p = le poids du lien (i,j)].
trouveMin(Q, d) qui renvoie et retire de Q (file de
sommets) le sommet i appartenant à Q qui a la plus
petite distance ; Càd d[i]=min([d[j]/j c Q]).
dijkstra(M, Sdeb, Sfin) qui renvoie le chemin le plus
cours entre du sommet Sdeb vers le sommet Sfin.
