L'algorithme de Dijkstra offre une solution plus efficace pour trouver le chemin le plus court dans un graphe lorsque toutes les valeurs des arêtes sont positives.

Entrées

• G = (V, E) : Graphe avec une valuation positive c des arêtes.
• s : Un sommet de V.

Étapes de l'algorithme

1. Initialisation :
   • Initialiser tous les sommets à non marqué.
   • Initialiser tous les labels L à +∞.
   • Attribuer L(s) := 0 (le label du sommet de départ est 0).
2. Boucle principale :
   • Tant qu'il existe un sommet non marqué :
     • Sélection du sommet le plus proche :
       • Choisir le sommet y non marqué ayant le plus petit label L.
       • Marquer y.
     • Mise à jour des labels des voisins :
       • Pour chaque sommet z non marqué voisin de y :
         • Mettre à jour : L(z) := min{ L(z), L(y) + c(y, z) }.
       • Fin Pour.
   • Fin Tant que.
3. Résultat :
   • Pour tout sommet x de V, la longueur du plus court chemin de s à x est donnée par :D(x) = L(x).

Exemple

Exercices