Introduction

Dans cet article je voudrais partager une implémentation de l’algorithme de Dijkstra.

Cet algorithme est utilisé pour calculer le chemin le plus court entre deux points dans une matrice, dans la vraie vie ce type d’algorithmes est utilisée dans des outils comme google maps, Waze, tomtom … pour calculer la route à suivre entre deux points dans une carte.

c’est aussi utilisé dans le domaine du jeux-vidéo dans des jeux vidéo.

Description rapide de l’algorithme

Je vous invite à regarder cette vidéo pour une description détaillée de l’algorithme.

c’est très bien expliqué et ça va droit au but, tout ce que j’aime.

Demo

Vous pouvez tester mon implémentation sur cette URL.

J’ai essayé de donner un cas d’utilisation réel, dans mon exemple je simule un scénario de recherche de chemin entre deux poins d’une carte.

vous remarquerez différentes couleurs de lignes entre les différents points représentant l’état du trafic entre 2 points:

• Gris: Pour un trafic normale
• Jaune: Pour un trafic moin fluide ( en cas de travaux par exemple)
• Rouge: trafic complétement congéstionné, donc chemin à éviter dans la mesure du possible.

Commencez donc par cliquer sur les différentes routes pour changer leur état.

après cela choisissez votre point de départ, point d’arrivée puis lancez la recherche en cliquant sur « GO »

Code source

Vous pouvez trouver le code source sur github.

Comment lire le code

Le code est divisé principalement en 3 parties:

Partie 1 : Implémentation de l’algorithme de Dijkstra dans le fichier src/dijkstra/dijkstra.ts
Partie 2: Positionnement des différents noeuds dans l’écran avec le composant src/components/Visualizer.vue
Partie 3: La page principale qui regroupe tout les composants, ici on va définir les données d’exemple, et définir le design finale de la page.