Algorithme de chemin le plus court de Dijkstra - Une introduction détaillée et visuelle

Bienvenue! Si vous avez toujours voulu apprendre et comprendre l'algorithme de Dijkstra, cet article est pour vous. Vous verrez comment cela fonctionne dans les coulisses avec une explication graphique étape par étape.

Tu vas apprendre:

  • Concepts de base des graphes (un examen rapide).
  • À quoi sert l'algorithme de Dijkstra.
  • Comment cela fonctionne dans les coulisses avec un exemple étape par étape.

Commençons. ✨

🔹 Introduction aux graphiques

Commençons par une brève introduction aux graphiques.

Concepts de base

Les graphiques sont des structures de données utilisées pour représenter des «connexions» entre des paires d'éléments.

  • Ces éléments sont appelés nœuds . Ils représentent des objets, des personnes ou des entités de la vie réelle.
  • Les connexions entre les nœuds sont appelées arêtes .

Ceci est une représentation graphique d'un graphique:

Les nœuds sont représentés avec des cercles colorés et les bords sont représentés avec des lignes qui relient ces cercles.

💡 Astuce: deux nœuds sont connectés s'il y a une arête entre eux.

Applications

Les graphiques sont directement applicables aux scénarios du monde réel. Par exemple, nous pourrions utiliser des graphiques pour modéliser un réseau de transport où les nœuds représenteraient les installations qui envoient ou reçoivent des produits et les bords représenteraient des routes ou des chemins qui les relient (voir ci-dessous).

Types de graphiques

Les graphiques peuvent être:

  • Non dirigé: si pour chaque paire de nœuds connectés, vous pouvez passer d'un nœud à l'autre dans les deux sens.
  • Dirigé: si pour chaque paire de nœuds connectés, vous ne pouvez aller d'un nœud à l'autre que dans une direction spécifique. Nous utilisons des flèches au lieu de simples lignes pour représenter les arêtes dirigées.

💡 Astuce: dans cet article, nous travaillerons avec des graphiques non orientés.

Graphiques pondérés

Un graphe de poids est un graphe dont les arêtes ont un «poids» ou un «coût». Le poids d'un bord peut représenter la distance, le temps ou tout ce qui modélise la "connexion" entre la paire de nœuds qu'il relie.

Par exemple, dans le graphique pondéré ci-dessous, vous pouvez voir un nombre bleu à côté de chaque bord. Ce nombre est utilisé pour représenter le poids de l'arête correspondante.

💡 Conseil: ces poids sont essentiels pour l'algorithme de Dijkstra. Vous verrez pourquoi dans un instant.

🔸 Introduction à l'algorithme de Dijkstra

Maintenant que vous connaissez les concepts de base des graphiques, commençons à plonger dans cet algorithme étonnant.

  • Objectif et cas d'utilisation
  • Histoire
  • Bases de l'algorithme
  • Exigences

Objectif et cas d'utilisation

Avec l'algorithme de Dijkstra, vous pouvez trouver le chemin le plus court entre les nœuds d'un graphe. En particulier, vous pouvez trouver le chemin le plus court d'un nœud (appelé "nœud source") à tous les autres nœuds du graphe , produisant un arbre du chemin le plus court.

Cet algorithme est utilisé dans les appareils GPS pour trouver le chemin le plus court entre l'emplacement actuel et la destination. Il a de larges applications dans l'industrie, en particulier dans les domaines qui nécessitent la modélisation de réseaux.

Histoire

Cet algorithme a été créé et publié par le Dr Edsger W. Dijkstra, un brillant informaticien et ingénieur logiciel néerlandais.

En 1959, il publie un article de 3 pages intitulé "Une note sur deux problèmes liés aux graphes" où il explique son nouvel algorithme.

Lors d'un entretien en 2001, le Dr Dijkstra a révélé comment et pourquoi il avait conçu l'algorithme:

Quel est le moyen le plus court pour voyager de Rotterdam à Groningue? C'est l'algorithme du chemin le plus court, que j'ai conçu en 20 minutes environ. Un matin, je faisais du shopping à Amsterdam avec ma jeune fiancée, et fatigués, nous nous sommes assis sur la terrasse du café pour boire une tasse de café et je me demandais juste si je pouvais le faire, et j'ai ensuite conçu l'algorithme pour le chemin le plus court. . Comme je l'ai dit, c'était une invention de 20 minutes. En fait, il a été publié en 1959, trois ans plus tard. La publication est toujours assez sympa. L'une des raisons pour lesquelles il est si beau est que je l'ai conçu sans crayon ni papier. Sans crayon ni papier, vous êtes presque obligé d'éviter toutes les complexités évitables. Finalement, cet algorithme est devenu, à ma grande stupéfaction, l'une des pierres angulaires de ma renommée. - Comme cité dans l'article Edsger W.Dijkstra d'après une interview avec Edsger W. Dijkstra.

Incroyable, non? En seulement 20 minutes, le Dr Dijkstra a conçu l'un des algorithmes les plus célèbres de l'histoire de l'informatique.

Bases de l'algorithme de Dijkstra

  • L'algorithme de Dijkstra commence essentiellement au nœud que vous choisissez (le nœud source) et analyse le graphique pour trouver le chemin le plus court entre ce nœud et tous les autres nœuds du graphique.
  • L'algorithme garde une trace de la distance la plus courte actuellement connue de chaque nœud au nœud source et il met à jour ces valeurs s'il trouve un chemin plus court.
  • Une fois que l'algorithme a trouvé le chemin le plus court entre le nœud source et un autre nœud, ce nœud est marqué comme "visité" et ajouté au chemin.
  • Le processus se poursuit jusqu'à ce que tous les nœuds du graphique aient été ajoutés au chemin. De cette façon, nous avons un chemin qui relie le nœud source à tous les autres nœuds en suivant le chemin le plus court possible pour atteindre chaque nœud.

Exigences

L'algorithme de Dijkstra ne peut fonctionner qu'avec des graphiques qui ont des poids positifs . En effet, pendant le processus, les poids des arêtes doivent être ajoutés pour trouver le chemin le plus court.

S'il y a un poids négatif dans le graphique, alors l'algorithme ne fonctionnera pas correctement. Une fois qu'un nœud a été marqué comme "visité", le chemin actuel vers ce nœud est marqué comme le chemin le plus court pour atteindre ce nœud. Et les poids négatifs peuvent modifier cela si le poids total peut être décrémenté après cette étape.

🔹 Exemple de l'algorithme de Dijkstra

Maintenant que vous en savez plus sur cet algorithme, voyons comment il fonctionne dans les coulisses avec un exemple étape par étape.

Nous avons ce graphique:

L'algorithme générera le chemin le plus court du nœud 0vers tous les autres nœuds du graphe.

💡 Astuce: Pour ce graphique, nous supposerons que le poids des arêtes représente la distance entre deux nœuds.

Nous aurons le chemin le plus court de nœud 0en nœud 1, de nœud 0en nœud 2, de nœud 0en nœud 3, et ainsi de suite pour chaque nœud du graphique.

Au départ, nous avons cette liste de distances (veuillez consulter la liste ci-dessous):

  • La distance entre le nœud source et lui-même est 0. Pour cet exemple, le nœud source sera node 0mais il peut s'agir de n'importe quel nœud de votre choix.
  • La distance entre le nœud source et tous les autres nœuds n'a pas encore été déterminée, nous utilisons donc le symbole de l'infini pour le représenter initialement.

Nous avons également cette liste (voir ci-dessous) pour garder une trace des nœuds qui n'ont pas encore été visités (nœuds qui n'ont pas été inclus dans le chemin):

💡 Astuce: n'oubliez pas que l'algorithme est terminé une fois que tous les nœuds ont été ajoutés au chemin.

Puisque nous choisissons de commencer au nœud 0, nous pouvons marquer ce nœud comme visité. De manière équivalente, nous le rayons de la liste des nœuds non visités et ajoutons une bordure rouge au nœud correspondant dans le diagramme:

Nous devons maintenant commencer à vérifier la distance entre le nœud 0et ses nœuds adjacents. Comme vous pouvez le voir, ce sont des nœuds 1et 2(voir les bords rouges):

💡 Astuce: cela ne signifie pas que nous ajoutons immédiatement les deux nœuds adjacents au chemin le plus court. Avant d'ajouter un nœud à ce chemin, nous devons vérifier si nous avons trouvé le chemin le plus court pour l'atteindre. Nous faisons simplement un processus d'examen initial pour voir les options disponibles.

Nous devons mettre à jour les distances de nœud 0à nœud 1et nœud 2avec les poids des arêtes qui les relient au nœud 0(le nœud source). Ces poids sont respectivement de 2 et 6:

Après avoir mis à jour les distances des nœuds adjacents, nous devons:

  • Sélectionnez le nœud le plus proche du nœud source en fonction des distances connues actuelles.
  • Marquez-le comme visité.
  • Ajoutez-le au chemin.

Si nous vérifions la liste des distances, nous pouvons voir que le nœud 1a la distance la plus courte au nœud source (une distance de 2), nous l'ajoutons donc au chemin.

Dans le diagramme, nous pouvons représenter cela avec un bord rouge:

Nous le marquons avec un carré rouge dans la liste pour indiquer qu'il a été "visité" et que nous avons trouvé le chemin le plus court vers ce nœud:

Nous le rayons de la liste des nœuds non visités:

Nous devons maintenant analyser les nouveaux nœuds adjacents pour trouver le chemin le plus court pour les atteindre. Nous analyserons uniquement les nœuds adjacents aux nœuds qui font déjà partie du chemin le plus court (le chemin marqué avec des arêtes rouges).

Le nœud 3et le nœud 2sont tous deux adjacents aux nœuds qui se trouvent déjà dans le chemin car ils sont directement connectés au nœud 0et au nœud 1, respectivement, comme vous pouvez le voir ci-dessous. Ce sont les nœuds que nous analyserons à l'étape suivante.

Puisque nous avons déjà la distance entre le nœud source et le nœud 2inscrit dans notre liste, nous n'avons pas besoin de mettre à jour la distance cette fois. Il suffit de mettre à jour la distance entre le nœud source et le nouveau nœud adjacent (nœud 3):

Cette distance est de 7 . Voyons pourquoi.

Pour trouver la distance entre le nœud source et un autre nœud (dans ce cas, le nœud 3), nous ajoutons les poids de toutes les arêtes qui forment le chemin le plus court pour atteindre ce nœud:

  • Pour le nœud 3: la distance totale est de 7 car on ajoute les poids des arêtes qui forment le chemin 0 -> 1 -> 3(2 pour l'arête 0 -> 1et 5 pour l'arête 1 -> 3).

Maintenant que nous avons la distance aux nœuds adjacents, nous devons choisir quel nœud sera ajouté au chemin. Nous devons sélectionner le nœud non visité avec la distance la plus courte (actuellement connue) du nœud source.

À partir de la liste des distances, nous pouvons immédiatement détecter qu'il s'agit d'un nœud 2de distance 6 :

Nous l'ajoutons au chemin graphiquement avec une bordure rouge autour du nœud et une bordure rouge:

Nous le marquons également comme visité en ajoutant un petit carré rouge dans la liste des distances et en le rayant de la liste des nœuds non visités:

Maintenant, nous devons répéter le processus pour trouver le chemin le plus court du nœud source au nouveau nœud adjacent, qui est nœud 3.

Vous pouvez voir que nous avons deux chemins possibles 0 -> 1 -> 3ou 0 -> 2 -> 3. Voyons comment nous pouvons décider lequel est le chemin le plus court.

Le nœud a 3déjà une distance dans la liste qui a été enregistrée précédemment ( 7, voir la liste ci-dessous). Cette distance était le résultat d'une étape précédente, où nous avons ajouté les poids 5 et 2 des deux arêtes que nous devions croiser pour suivre le chemin 0 -> 1 -> 3.

Mais maintenant, nous avons une autre alternative. Si nous choisissons de suivre le chemin 0 -> 2 -> 3, nous aurions besoin de suivre deux arêtes 0 -> 2et 2 -> 3avec des poids 6 et 8 ,respectivement,ce qui représente une distance totale de 14 .

Clairement, la première distance (existante) est plus courte (7 vs 14), nous choisirons donc de conserver le chemin d'origine 0 -> 1 -> 3. Nous ne mettons à jour la distance que si le nouveau chemin est plus court.

Par conséquent, nous ajoutons ce nœud sur le chemin en utilisant la première alternative: 0 -> 1 -> 3.

Nous marquons ce nœud comme visité et le rayons de la liste des nœuds non visités:

Maintenant, nous répétons le processus à nouveau.

Nous devons vérifier les nouveaux nœuds adjacents que nous n'avons pas visités jusqu'à présent. Cette fois, ces nœuds sont nœud 4et nœud 5puisqu'ils sont adjacents au nœud 3.

Nous mettons à jour les distances de ces nœuds au nœud source, en essayant toujours de trouver un chemin plus court, si possible:

  • Pour le nœud 4: la distance est de 17 du chemin   0 -> 1 -> 3 -> 4.
  • Pour le nœud 5: la distance est de 22 à partir du chemin 0 -> 1 -> 3 -> 5.

💡 Astuce: notez que nous ne pouvons envisager d'étendre que le chemin le plus court (marqué en rouge). Nous ne pouvons pas considérer les chemins qui nous mèneront à travers des arêtes qui n'ont pas été ajoutées au chemin le plus court (par exemple, nous ne pouvons pas former un chemin qui passe par le bord 2 -> 3).

Nous devons choisir quel nœud non visité sera marqué comme visité maintenant. Dans ce cas, c'est le nœud 4car il a la distance la plus courte dans la liste des distances. Nous l'ajoutons graphiquement dans le diagramme:

Nous le marquons également comme "visité" en ajoutant un petit carré rouge dans la liste:

Et nous le rayons de la liste des nœuds non visités:

Et nous répétons le processus à nouveau. Nous vérifions les nœuds adjacents: nœud 5et nœud 6. Nous devons analyser chaque chemin possible que nous pouvons suivre pour les atteindre à partir de nœuds qui ont déjà été marqués comme visités et ajoutés au chemin.

Pour le nœud 5:

  • La première option est de suivre le chemin 0 -> 1 -> 3 -> 5, qui a une distance de 22 du nœud source (2 + 5 + 15). Cette distance était déjà enregistrée dans la liste des distances lors d'une étape précédente.
  • La deuxième option serait de suivre le chemin 0 -> 1 -> 3 -> 4 -> 5, qui a une distance de 23 du nœud source (2 + 5 + 10 + 6).

Clairement, le premier chemin est plus court, nous le choisissons donc pour node 5.

Pour le nœud 6:

  • Le chemin disponible est 0 -> 1 -> 3 -> 4 -> 6, qui a une distance de 19 du nœud source (2 + 5 + 10 + 2).

Nous marquons le nœud avec la distance la plus courte (actuellement connue) comme visité. Dans ce cas, node 6.

Et nous le rayons de la liste des nœuds non visités:

Maintenant, nous avons ce chemin (marqué en rouge):

Un seul nœud n'a pas encore été visité, node 5. Voyons comment nous pouvons l'inclure dans le chemin.

Il existe trois chemins différents que nous pouvons emprunter pour atteindre le nœud à 5partir des nœuds qui ont été ajoutés au chemin:

  • Option 1:0 -> 1 -> 3 -> 5 avec une distance de 22 (2 + 5 + 15).
  • Option 2:0 -> 1 -> 3 -> 4 -> 5 avec une distance de 23 (2 + 5 + 10 + 6).
  • Option 3:0 -> 1 -> 3 -> 4 -> 6 -> 5 avec une distance de 25 (2 + 5 + 10 + 2 + 6).

Nous sélectionnons le chemin le plus court: 0 -> 1 -> 3 -> 5avec une distance de 22 .

Nous marquons le nœud comme visité et le rayons de la liste des nœuds non visités:

Et voilà! Nous avons le résultat final avec le chemin le plus court du nœud 0à chaque nœud du graphique.

Dans le diagramme, les lignes rouges marquent les arêtes appartenant au chemin le plus court. Vous devez suivre ces arêtes pour suivre le chemin le plus court pour atteindre un nœud donné dans le graphique à partir du nœud 0.

Par exemple, si vous souhaitez atteindre le nœud à 6partir du nœud 0, il vous suffit de suivre les bords rouges et vous suivrez 0 -> 1 -> 3 -> 4 - > 6automatiquement le chemin le plus court .

🔸 En résumé

  • Les graphiques sont utilisés pour modéliser les connexions entre des objets, des personnes ou des entités. Ils ont deux éléments principaux: les nœuds et les arêtes. Les nœuds représentent des objets et les arêtes représentent les connexions entre ces objets.
  • L'algorithme de Dijkstra trouve le chemin le plus court entre un nœud donné (qui est appelé le «nœud source») et tous les autres nœuds d'un graphe.
  • Cet algorithme utilise les poids des arêtes pour trouver le chemin qui minimise la distance totale (poids) entre le nœud source et tous les autres nœuds.

J'espère vraiment que vous avez aimé mon article et que vous l'avez trouvé utile. Vous savez maintenant comment l'algorithme de Dijkstra fonctionne dans les coulisses. Suivez-moi sur Twitter @EstefaniaCassN et consultez mes cours en ligne.