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

Alizé Turpin
Par 
Alizé Turpin
Directrice des Admissions
Dernière mise à jour le 
09
 
November
 
2023
Devenez Data Scientist et donnez un tournant décisif à votre carrière !
Découvrir notre formation
Qu'est-ce que l'algorithme de Dijkstra ?
Sommaire

Les graphes sont utilisés dans de nombreux domaines, en particulier celui de l'informatique. Ils permettent de structurer des données et servent ainsi à modéliser les relations qui existent entre elles. Les images peuvent être représentées sous forme de graphique de pixels, les phrases sous forme de graphiques de mots, etc. Grâce à l'algorithme Dijkstra, on recherche les chemins les plus courts entre les nœuds ou les sommets d'un graphe. C'est une étape importante pour les professionnels de la data qui ont recours à cet outil dans plusieurs situations. Qu'est-ce que l'algorithme de Dijkstra ? Comment fonctionne-t-il ? À quel moment son utilisation devient nécessaire ?

Devenez Data Scientist et donnez un tournant décisif à votre carrière !
Découvrir notre formation
Formation IAFormation IA

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.

Soirée Portes Ouvertes Jedha BootcampSoirée Portes Ouvertes Jedha Bootcamp
Alizé Turpin
Alizé Turpin
Directrice des Admissions
Alizé est l'une des premières membres de l'équipe Jedha. Elle a rejoint l'école en 2019 pour s'occuper des Admissions et a développé une expertise unique pour guider nos élèves dans la réalisation de leur projet de reconversion professionnelle. Alizé est également une entrepreneuse dans l'âme. En parallèle de son investissement chez Jedha, elle a créé plusieurs marques de mode et d'accessoires comme Cheffe de Meute, Don't Steal My Dog et Bumbies.

Articles recommandés

Intelligence Artificielle
Les 6 meilleures formations en Machine Learning
Vous souhaitez vous reconvertir dans la Data ? Découvrez les meilleures offres de formation en Machine Learning pour réussir votre projet professionnel !
Intelligence Artificielle
Méthodes de Machine Learning | Jedha
Différentes méthodes de travail existent en Machine Learning, découvrez ce qu'est une méthode Machine Learning, et comment évaluer son modèle ML.
Intelligence Artificielle
Algorithme Gradient Boosting, Présentation et fonctionnement | Jedha
L'algorithme de la descente de gradient, un algorithme en Machine Learning indispensable pour chaque Data Scientist. Comment utiliser cet algorithme ?
Blog
Qu'est-ce que la théorie des graphes ?
Théorie mathématique des plus utilisées, la théorie des graphes permet d'analyser de manière simplifiée un ensemble d'éléments ayant des liens les uns avec les autres.
Intelligence Artificielle
La vraie différence entre Machine Learning & Deep Learning | Jedha
Machine Learning & Deep Learning sont devenus des termes extrêmement utilisés dans le cadre de nos activités, avec des applications toujours plus nombreuses. Lorsque l’on parle de Deep Learning, nous parlons d’algorithmes capables de mimer les actions du cerveau humain grâce à des réseaux de neurones d’où le terme d’Intelligence Artificielle.
Intelligence Artificielle
Qu'est-ce que le KNN ? Le modèle de Machine Learning supervisé
L'algorithme KNN est un modèle de Machine Learning supervisé. Il est utilisé pour la régression et la classification des données.