L’algorithme de Dijkstra est un algorithme très connu dans le milieu académique informatique, à un certain niveau il n’existe pas un étudiant qui ne connaisse pas l’algorithme de Dijkstra ou n’avoir jamais entendu parler, la raison est que c’est un algorithme très utilisé en pratique, la manifestation de son utilisation la plus simple est sans doute la recherche du plus court chemin sur les navigateurs GPS des voitures ou sur Google map, il est surtout aussi bien connu dans son utilisation dans les protocoles de routage dans les réseaux informatiques, ça permet aux données de prendre le plus court chemin sur la toile d’internet.
La vidéo de la chaîne YouTube Computerphile est une explication de la manière dans l’algorithme fonctionne, l’algorithme de Dijkstra est un algorithme qui permet de trouver le plus court chemin dans un graphe, d’une manière simple, mathématiquement un graphe peut représenter des villes avec le chemin entre ces villes, il peut représenter les routeurs sur un réseau avec leurs connexions…etc. Malgré que les étapes par lesquelles l’algorithme passe semblent informes et compliqués ils sont aux contraires cohérents, consistants et logiques, supposons on demande à une personne de trouver le plus court chemin entre deux villes sur une carte avec de multiples villes et multiples chemins, il va intuitivement suivre les mêmes étapes de l’algorithme, ainsi il va commencer par choisir le chemin le plus court vers les villes voisines, garder la trace de tous les chemins et avancer d’une ville à l’autre, revenir sur un supposé long chemin s’il s’avère qu’il peut mener vers une ville donnée par un autre cours chemins et ainsi de suite. La façon de revenir vers d’anciens chemins est bien connue en algorithmique, ça s’appelle le backtracking, et l’algorithme de Dijkstra d’en fait parti ces algorithmes.