L’algorithme de Dijkstra, Edsger Dijkstra publié en 1959, est une méthode puissante pour trouver les chemins les plus courts entre les sommets dans un graphe. Ce Instructable contient les étapes de cet algorithme, pour vous aider à suivre l’algorithme sur papier ou sa mise en œuvre d’un programme.
Notez que les étapes indiquées seulement enregistrent les longueurs de chemin le plus court et ne pas enregistrer les réels plus courts chemins le long des sommets. Si la connaissance de la composition des chemins est souhaitée, étapes 2 et 4 peuvent être facilement modifiés pour enregistrer ces données dans un autre tableau associatif : voir article de 1959 de Dijkstra dans Numerische Mathematik pour plus d’informations.
Bon, commençons ! Dans ces instructions, nous supposons que nous avons les informations suivantes :
- Un graphe G
- Un ensemble de sommets V
- Un ensemble d’arêtes E (où chaque arête a un poids non négatif)
- Point de départ s ∈ V
Notez que le « élément de » symbole ∈, indique que l’élément du côté gauche du symbole est contenu dans la collection de l’autre côté du symbole. Par exemple, s ∈ V indique que s est un élément de V --dans ce cas, cela signifie que s est un sommet contenu dans le graphique.
Ces directions sont conçues pour une utilisation par un public familier avec les bases de la théorie des graphes, théorie des ensembles et des structures de données. Avec cette connaissance préalable, toute notation et concepts utilisés devraient être relativement simples pour le public.
Pour plus d’informations sur les détails de l’algorithme de Dijkstra, la page Wikipedia sur c’est une excellente ressource.