Lire ceci dans d’autres langues : English, 한국어, 日本語, 简体中文, 繁體中文, Українська, Español, Français, Deutsch, עברית
L’algorithme de Dijkstra est un algorithme permettant de trouver les plus courts chemins entre des nœuds dans un graphe, pouvant représenter, par exemple, un réseau routier.
Il existe plusieurs variantes de cet algorithme. La version originale de Dijkstra trouvait le plus court chemin entre deux nœuds, mais la version la plus courante fixe un seul nœud comme « nœud source » et calcule les plus courts chemins de cette source vers tous les autres nœuds du graphe, produisant ainsi un arbre des plus courts chemins.
L’algorithme de Dijkstra trouve le plus court chemin entre a et b.
Il sélectionne le sommet non visité avec la plus petite distance, calcule la distance à travers ce sommet vers chacun de ses voisins non visités, et met à jour la distance du voisin si celle-ci est plus courte.
Le sommet est ensuite marqué comme visité (en rouge) lorsque tous ses voisins ont été traités.
- Systèmes GPS / navigation
- Optimisation des itinéraires de transport public et d’avions
- Routage Internet (protocoles OSPF, IS-IS)
- Optimisation du trafic et de la latence réseau
- Recherche de chemin dans les jeux vidéo (chemin le plus court sur une carte)
- Optimisation des itinéraires de livraison et de logistique
- Conception de réseaux de transport et de chaînes d’approvisionnement
Supposons que nous ayons un graphe pondéré de nœuds, où chaque arête possède une distance entre deux nœuds.
Par exemple, la distance entre le nœud A et le nœud B est de 7 mètres (ou simplement 7m).
L’algorithme utilise une file de priorité pour toujours extraire le prochain sommet non visité ayant la plus petite distance depuis le nœud d’origine.
Le nœud de départ, par définition, a une distance de 0m depuis lui-même.
Nous commençons donc avec ce nœud, le seul présent dans la file de priorité au départ.
Les autres nœuds seront ajoutés à la file de priorité plus tard, pendant la traversée du graphe (en visitant les voisins).
Chaque voisin du nœud extrait de la file est parcouru afin de calculer la distance à partir du nœud d’origine.
Par exemple, la distance de A à B est 0m + 7m = 7m.
Chaque fois qu’un voisin encore non visité est découvert, il est ajouté à la file de priorité, la priorité correspondant à la distance depuis le nœud d’origine.
Le nœud B est ajouté à la file de priorité minimale pour être traité plus tard.
Nous visitons le voisin suivant, C, du nœud A.
La distance depuis le nœud d’origine A vers C est 0m + 9m = 9m.
Le nœud C est ajouté à la file de priorité minimale pour être parcouru ultérieurement.
Même chose pour le nœud F.
La distance actuelle de A à F est 0m + 14m = 14m.
Le nœud F est ajouté à la file de priorité minimale pour être visité plus tard.
Une fois que tous les voisins du nœud actuel ont été examinés, ce nœud est ajouté à l’ensemble visited.
Nous ne souhaitons plus revisiter ces nœuds lors des prochaines itérations.
Nous extrayons maintenant de la file le nœud le plus proche de la source (celui ayant la plus courte distance) et commençons à visiter ses voisins.
Si le nœud que nous visitons (dans ce cas, C) est déjà présent dans la file, cela signifie que sa distance a déjà été calculée via un autre chemin (A → C).
Si la nouvelle distance (depuis le chemin A → B → C) est plus courte, nous mettons à jour la distance dans la file de priorité.
Si elle est plus longue, nous la laissons telle quelle.
En visitant le nœud C via B (chemin A → B → C), nous trouvons que la distance est 7m + 10m = 17m.
Ceci est plus long que la distance enregistrée de 9m pour le chemin A → C.
Dans ce cas, nous ignorons simplement cette distance plus longue.
Nous visitons un autre voisin de B, à savoir D.
La distance vers D est 7m + 15m = 22m.
Comme D n’a pas encore été visité et n’est pas dans la file, nous l’ajoutons avec une priorité (distance) de 22m.
À ce stade, tous les voisins de B ont été parcourus, donc nous ajoutons B à l’ensemble visited.
Ensuite, nous extrayons de la file le nœud le plus proche du nœud d’origine.
Nous parcourons les voisins non visités du nœud C.
La distance vers F via C (chemin A → C → F) est 9m + 2m = 11m.
C’est plus court que la distance précédemment enregistrée de 14m pour le chemin A → F.
Nous mettons donc à jour la distance de F à 11m et ajustons sa priorité dans la file.
Nous venons de trouver un chemin plus court vers F.
Même chose pour D.
Nous avons trouvé un chemin plus court vers D : A → C → D est plus court que A → B → D.
Nous mettons à jour la distance de 22m à 20m.
Tous les voisins de C ont été parcourus, donc nous pouvons ajouter C à l’ensemble visited.
Nous extrayons maintenant de la file le prochain nœud le plus proche, F.
Nous enregistrons la distance vers E comme 11m + 9m = 20m.
Nous ajoutons F à l’ensemble visited et extrayons ensuite D, le prochain nœud le plus proche.
La distance vers E via D est 20m + 6m = 26m.
C’est plus long que la distance déjà calculée depuis F (20m).
Nous pouvons donc ignorer cette distance plus longue.
Le nœud D est maintenant visité.
Le nœud E est maintenant visité également.
La traversée du graphe est terminée.
Nous connaissons maintenant les distances les plus courtes vers chaque nœud depuis le nœud de départ A.
En pratique, pendant le calcul des distances, on enregistre également les previousVertices (nœuds précédents) pour pouvoir reconstruire la séquence exacte des nœuds qui forment le chemin le plus court.
Par exemple, le chemin le plus court de A à E est A → C → F → E.