Trouvez le chemin le plus court entre deux points sur un graphique avec l'algorithme de Dijkstra

Trouver le chemin le plus court entre deux points sur un graphique est un problème courant dans les structures de données, en particulier lorsqu'il s'agit d'optimisation.

Un graphe est une série de nœuds reliés par des arêtes. Les graphiques peuvent être pondérés (les bords portent des valeurs) et directionnels (les bords ont une direction).

Certaines applications de ceci sont l'optimisation de la trajectoire de vol ou 6 degrés de Kevin Bacon.

Algorithme de Dijkstra

La solution la plus courante pour ce problème est l'algorithme de Dijkstra qui met à jour le chemin le plus court entre le nœud actuel et tous ses voisins.

Après avoir mis à jour la distance de tous les voisins, il se déplace vers le nœud avec la distance la plus basse et répète le processus avec tous les voisins non visités. Ce processus se poursuit jusqu'à ce que tout le graphique ait été visité.

Image des niveaux de code

Étape 0:

Notre graphique doit être configuré pour que nous puissions enregistrer les valeurs requises. Sur n'importe quel bord, nous avons la distance entre les deux nœuds qu'il relie. Sur n'importe quel nœud, nous avons sa distance la plus courte du nœud de départ.

Définissons la valeur de chaque nœud sur l'infini positif et définissons la valeur du nœud de départ sur zéro.

Étape 1:

Regardez tous les nœuds directement adjacents au nœud de départ. Les valeurs portées par les arêtes reliant le départ et ces nœuds adjacents sont les distances les plus courtes vers chaque nœud respectif.

Enregistrez ces distances sur le nœud - écrasant l'infini - et rayez également les nœuds, ce qui signifie que leur chemin le plus court a été trouvé.

Étape 2:

Sélectionnez l'un des nœuds dont le chemin le plus court a été calculé, nous l'appellerons notre pivot. Regardez les nœuds adjacents (nous les appellerons nos nœuds de destination) et les distances qui les séparent.

Pour chaque nœud de destination:

  • Si la valeur du pivot plus la valeur du bord qui le connecte est inférieure à la valeur du nœud de destination, mettez à jour sa valeur, car un nouveau chemin plus court a été trouvé.
  • Si tous les itinéraires vers ce nœud de destination ont été explorés, il peut être barré.

Étape 3:

Répétez l'étape 2 jusqu'à ce que tous les nœuds aient été barrés. Nous avons maintenant un graphique où les valeurs contenues dans n'importe quel nœud seront la distance la plus courte à partir du nœud de départ.

Plus d'information:

En savoir plus sur l'algorithme de Dijkstra

Autres algorithmes de chemin le plus court