Cours Graphes
Algorithme de Dijkstra
Lancer le programme
Accède gratuitement à cette vidéo pendant 7 jours Profite de ce cours et de tout le programme de ta classe avec l'essai gratuit de 7 jours !

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$. 

graphe_dijskra

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

Il reste 70% de cette fiche de cours à lire
Cette fiche de cours est réservée uniquement à nos abonnés. N'attends pas pour en profiter, abonne-toi sur lesbonsprofs.com. Tu pourras en plus accéder à l'intégralité des rappels de cours en vidéo ainsi qu'à des QCM et des exercices d'entraînement avec corrigé en texte et en vidéo.