Qu'est-ce que l'algorithme de Dijkstra ?

Qu'est-ce que l'algorithme de Dijkstra ?

L'algorithme de Dijkstra est un algorithme utilisé en théorie des graphes pour la résolution du problème du plus court chemin. Quand on recherche le parcours le plus court entre deux sommets (ou nœuds) d'un graphe, on peut être tenté d'énumérer l'ensemble des chemins possibles entre ces sommets afin de calculer leur longueur et déterminer la plus courte distance (dist). Cependant, face à un graphe de taille importante, ce procédé ne peut plus être envisagé. L'utilisation des algorithmes pour identifier le chemin le plus court entre les sommets en partant d'un sommet ou nœud de départ est donc indispensable. On retrouve d'ailleurs cette notion de 'nœud' avec l'algorithme de Machine Learning, l'arbre de décision, qui permet de faire une prédiction ou un classement. L'algorithme le plus connu pour trouver cet élément est celui de Dijkstra, publié en 1959 et inventé par Edsger Dijkstra, un informaticien néerlandais.

On pourra se servir de cet algorithme pour déterminer le chemin le plus court pour rejoindre une ville par exemple, à partir des données sur le réseau routier d'une région. C'est un moyen de calculer les plus courts chemins en partant d'un nœud (ou sommet) vers tous les autres sommets ou d'un sommet initial vers un sommet d'arrivée. Le graphe est dit orienté, avec des arcs ou des arêtes pondérées par des valeurs positives. Pour ce type de graphe, les arêtes sont également appelées des arcs.

‍

Fonctionnement

Le principe de l'algorithme de Dijkstra est de procéder à la recherche du chemin avec le poids le plus faible entre deux nœuds ou sommets. Le poids de chemin représentant la somme des poids des arcs ou des arêtes qui le compose. Dans l'exemple du réseau routier, les villes sont représentées par les sommets du graphe et les routes qui les relient sont les arêtes ou les arcs. Chaque arc ou arête du graphe correspond à un élément, le poids de l'arc, représentant ici la distance entre deux villes.

L'algorithme de Dijkstra se base sur le parcours en largeur pour trouver la réponse au problème du plus court chemin à partir du point de départ. Il va garder en mémoire le parcours le plus court depuis l'endroit initial pour chacune des villes au sein d'un tableau. On dit que l'algorithme recherche les « fils » du nœud où l'on se trouve, le sommet initial étant le nœud père.

Dijkstra nécessite l'implémentation d'une file de priorité. On pourra ainsi voir le jeu des structures de données dans le calcul de la complexité de l'algorithme. Du point initial, le sommet ou le nœud accessible de distance minimale (dist) est d'abord visité. À partir de ce sommet, on visite le sommet voisin, puis celui qui suit. L'algorithme visite tous les nœuds voisins en mettant à jour la distance quand elle est inférieure à celle reportée auparavant dans la liste.

L'opération est répétée jusqu'à la visite du point d'arrivée ou jusqu'à ce que l'ensemble des sommets du graphe soit visité. Cela permet d'avoir un ensemble, arbre du plus court chemin, qui conserve la trace des sommets faisant partie de l'arbre de chemin le plus court, autrement dit la distance minimale (dist) de la source calculée et finalisée.

Quand utiliser Dijkstra ?

Dijkstra est un algorithme qui est utilisé dans plusieurs situations réelles. Avec les services de cartographie numérique dans Google Maps nous avons la possibilité de trouver la distance d'une ville à une autre ou de notre position de départ jusqu'à l'emplacement désiré le plus proche. Parmi tous les chemins qui relient l'emplacement de départ à celui souhaité, l'application accorde la priorité à celui ayant une distance minimale nommée dist. Elle utilise l'algorithme de Dijkstra pour indiquer l'itinéraire le plus court après avoir visité les sommets ou établit une liste des chemins les plus appropriés à partir de votre noeud de départ.

Les suggestions de liste d'amis sur les réseaux sociaux sont généralement effectuées en utilisant le même principe. L'algorithme de Dijkstra peut être appliqué pour trouver le chemin le plus court entre les utilisateurs, mesuré ici non par la distance, mais par les connexions existantes entre eux. Les drones automatisés utilisés pour une tâche spécifique comme la livraison de colis font également usage de cet algorithme. Une fois la source et la destination connues, l'application de Dijkstra permet à l'appareil de se déplacer dans la direction choisie en suivant le chemin le plus court pour réaliser sa mission en un temps minimal.

Comment apprendre Dijkstra ?

Vous pouvez apprendre Dijkstra à travers notre formation data scientist comportant des cours sur la théorie des graphes. Jedha propose des formations à distance et en présentiel de plusieurs niveaux. Destinés aux débutants, la formation Data Essentials part de l'analyse pure et dure des données à l'apprentissage des algorithmes et leur utilisation dans l'exécution d'un projet. Les étudiants reçoivent les bases sur la data visualisation, les langages de programmation, le machine learning, l'intelligence artificielle, etc.

Avec notre formation Data Fullstack, vous devenez un véritable professionnel. Elle permet de maîtriser l'ensemble du pipeline Data, de la collecte des données à la création d'algorithmes et leur mise en production sur une application web. Vous obtenez le certificat de « Concepteur développeur en Science des données » et êtes en mesure de gérer différents types de projets nécessitant par exemple l'utilisation de l'algorithme Dijkstra.

Enfin, la formation Lead permet de perfectionner ses compétences sur la gestion d'infrastructures complexes et les méthodes utilisées par les Data scientists. Ce sont des cours très pratiques où vous apprenez de véritables professionnels du domaine avec un parcours remarquable dans la Data.

‍