Embed Size (px)
DESCRIPTION
On cherche le plus court chemin de E à S sur le graphe suivant :. Pour démarrer, on marque à l'encre (rouge) le sommet E avec le poids 0, puisque le plus court chemin de E à E est évidemment de longueur 0. 0. - PowerPoint PPT Presentation
Citation preview
On cherche le plus court chemin de Eà S sur le graphe suivant :
Pour démarrer, on marque à l'encre (rouge) le sommet E avec le poids 0, puisque le plus court chemin de E à E est évidemment de longueur 0.
0
(3,E)
0
Chaque étape de l'algorithme consiste ensuite à exécuter les actions suivantes, tant que le sommet S à atteindre n'est pas marqué à l'encre.- Soit T le dernier sommet marqué à l'encre.- Pour tout sommet T' non encore marqué à l'encre et adjacent à T, calculer la somme s du poids de T et du poids de l'arête reliant T à T' ;
(1,E)
si T' n'est pas encore marqué au crayon (bleu), marquer T' au crayon avec le poids s ; si T' est déjà marqué au crayon, remplacer (toujours au crayon) le poids provisoire de T' par s si s est plus petit (on a trouvé un chemin plus court), sinon garder le poids précédent.
(3,E)
0
(1,E)
Parmi tous les sommets marqués au crayon, en choisir un de poids minimum et marquer à l'encre ce poids.
(3,E)
(2,B)
0
(1,E)
On réitère l'opération tant que le sommet final S n'est pas marqué à l'encre.
(4,B)
(6,B)
(2,B)
0
(1,E)
On réitère l'opération tant que le sommet final S n'est pas marqué à l'encre.
(4,B)
(6,B)
(2,B)
0
(1,E)
(4,B)
(4,A)
(6,B)
(2,B)
0
(1,E)
(4,B)
(4,A)
(6,B)
On peut aussi bien choisir de rayer le chemin allant de B à C
(2,B)
0
(1,E)
(4,B)
(6,B)
(5,C)
(7,C)
(2,B)
0
(1,E)
(4,B)
(5,C)
(7,C)
(2,B)
0
(1,E)
(4,B)
(5,C)
(7,C)
(6,D)
(2,B)
0
(1,E)
Le sommet S est marqué à l ’encre, l ’algorithme s’arrête.
(4,A)
(5,C)
(6,D)
(2,B)
0
(1,E)
On retrouve le chemin en repartant de S.SDCBE EBCDS
(4,B)
(5,C)
(6,D)
On peut aussi utiliser un tableau pour noter les étapes successives de l ’algorithme.
0
0 3(E) 1(E) E (3,E)
(1,E)
Pour démarrer, on marque à l'encre (rouge) le sommet E avec le poids 0, puisque le plus court chemin de E à E est évidemment de longueur 0.
0
0 3(E) 1(E) E (2,B)
(1,E)
1(E)2(B) 4(B) 6(B) EB(4,B)
(6,B)
Pour démarrer, on marque à l'encre (rouge) le sommet E avec le poids 0, puisque le plus court chemin de E à E est évidemment de longueur 0.
0
0 3(E) 1(E) E (2,B)
(1,E)
1(E)2(B) 4(B) 6(B) EB(4,B)
(6,B)
2(B) EBA4(A)
Pour démarrer, on marque à l'encre (rouge) le sommet E avec le poids 0, puisque le plus court chemin de E à E est évidemment de longueur 0.
0
0 3(E) 1(E) E (2,B)
(1,E)
1(E)2(B) 4(B) 6(B) EB(4,B)
(5,C)
2(B) EBA
4(B) EBC
(7,C)
5(C) 7(C)
4(A)
Pour démarrer, on marque à l'encre (rouge) le sommet E avec le poids 0, puisque le plus court chemin de E à E est évidemment de longueur 0.
0
0 3(E) 1(E) E (2,B)
(1,E)
1(E)2(B) 4(B) 6(B) EB(4,B)
(5,C)
2(B) EBA
4(B) EBC
(7,C)
5(C) 7(C)
5(C) EBCD6(D)
4(A)
Pour démarrer, on marque à l'encre (rouge) le sommet E avec le poids 0, puisque le plus court chemin de E à E est évidemment de longueur 0.
0
0 3(E) 1(E) E (2,B)
(1,E)
1(E)2(B) 4(B) 6(B) EB(4,B)
(5,C)
2(B) EBA
4(B) EBC
(7,C)
5(C) 7(C)
5(C) 6(D) EBCD
6(D) EBCDS
4(A)
