Table des matières
Plus court chemin, Algorithme de Dijkstra
Pour les besoins de cette partie, considérons un réseau constitué de routeurs, sur lequel on indique les distances entre routeurs.
On souhaite trouver le plus court chemin entre deux sommets.
Algorithme de Dijkstra
Détaillons le déroulement de l'algorithme de Dijkstra en partant du sommet R1.
Je noterai par exemple |R1,R3| une distance d'un chemin de R1 à R3. Cette distance dépend du chemin pris et on cherche la plus petite valeur possible.
Dans l'algorithme, on associe progressivement chaque sommet à une valeur, un poids, qui représente la meilleure distance trouvée jusque là depuis le sommet de départ. Par exemple, si on écrit (R4,3), cela veut dire qu'à ce moment de l'exécution, la meilleure distance |R1,R4| est 3. Mais cela pourra changer.
Étape 1
Sélection du sommet de départ R1. On lui affecte une pondération de 0 puisque la distance |R1,R1| est 0. Tous les autres sont affectés pour l'instant d'une distance ∞.
Étape 2
Examen de tous les voisins non pris du dernier sommet pris (ici R1)
En empruntant l'arête R1 - R2, cela fait une distance |R1,R2| de 4, ce qui est mieux que ∞. On sélectionne donc l'arête R1 - R2 (en orange) et on indique que R2 est pour l'instant, au mieux, à une distance de 4 depuis R1. On fait de même pour les autres voisins de R1, c'est à dire R3 et R4.
Étape 3
Parmi tous les non pris, R3 est le plus proche de R1. On le sélectionne donc. On avait mis en surbrillance l'arête R1 - R3 ce qui indiquait que le meilleur chemin pour atteindre R3 était l'arête R1 - R3. Ceci ne changera plus, cet arête est définitivement validée.
Étape 4
R3 étant le dernier pris, on examine ses voisins non pris, R4 et R5. Puisque |R1,R3| = 1 et que R3 - R4 est pondéré 1, cela ferait, en passant par R3, |R1,R4| = 2 ce qui est mieux que le |R1,R4| = 3 antérieur. On change donc le poids de R4 en le mettant à 2. Il vaut donc mieux arriver à R4 depuis R3. On désélectionne l'arête R1 - R4 (grisée) et on sélectionne l'arête R3 - R4. Pas de commentaire sur R5.
Étape 5
Le meilleur sommet est maintenant R4. On le place parmi les pris. On sait aussi maintenant que la meilleure arête pour atteindre R4 sera R3 - R4 (en vert) et que cela ne changera plus.
Étape 6
Examen des voisins non pris de R4. Pas de commentaires pour R6 et R7. Si on voulait atteindre R2 en passant par R4, cela donnerait |R1,R2| = 7 ce qui est moins bien que |R1,R2| = 4 que l'on avait déjà. L'arête R4 - R2 peut donc être abandonnée (grisée).
Étape 7
Le meilleur sommet suivant est R2…
Étape 8
Le dernier voisin de R2 a envisager est R7, mais l'arête R2 - R7 n'améliore pas le chemin déjà connu jusque R7. On abandonne donc l'arête R2 - R7.
Étape 9
Sélection de R6…
Étape 10
Le passage par R6 n'améliore pas le parcours jusque R5 (R6 - R5 grisé) mais améliore le chemin jusque R7 (désélection de R4 - R7 et sélection de R6 - R7)
Étape 11
Sélection de R5 qui n'a plus de voisins à examiner.
Étape 12
Sélection de R7 qui n'a lus de voisins à examiner.
À la fin de cet algorithme, on sait à la fois la plus courte distance menant d'un certain sommet (ici R1) jusque tous les autres, et aussi les chemins permettant de réaliser ces plus courtes distances.
À faire
Faites le même travail, à partir de R1, avec le graphe suivant :
Implémentation
À faire
- Écrivez en pseudo-code une version de l'algorithme de Dijkstra.
Vous pourrez utiliser des fonctions comme ajouter sommet à la liste des pris, ou extraire le sommet de plus petit poids parmi les non pris ou successeurs de sommet… - Implémentez une fonction dijkstra dans la classe
WGraphcréée précédemment.