Fiche de cours
Algorithme de Dijkstra
Définition
L'algorithme de Dijkstra est un algorithme qui permet de calculer le plus court chemin entre deux sommets.
Exemple
On considère le graphe suivant, et on souhaite trouver le chemin le plus court entre $A$ et $G$.
On dessine un tableau pour représenter les différentes étapes de l'algorithme et on écrit sur la première ligne le nom des sommets par ordre alphabétiques.
La dernière colonne représente le choix à l'issue de chaque étape de l'algorithme.
On part de $A$ : on dispose de trois possibilités : soit on va en $B$, soit en $D$ soit en $C$.
En dessous de chacun des ces sommets, on inscrit sur la premier ligne les poids de chaque arrête puis on choisit le sommet qui présente l'arrête de poids moindre.
Si aucune arrête relit deux sommets, on indique une distance infinie dans le tableau.
On choisit donc le sommet $B$, et on peut ensuite rejoindre le sommet $C$ ou le sommet $D$ : on ne peut pas revenir en $A$.
Lors de l'étape précédente, on avait choisit un chemin de longueur 3, donc à chacune des di