Terminale > Mathématiques > Graphes > Annales - Graphes

ANNALES - GRAPHES

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 !

Démarrer l'essai gratuit

Algorithme de Dijkstra

Permalien

Télécharger la fiche de cours Les téléchargements sont réservés uniquements aux abonnés

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 distances inscrites sur les arêtes, on ajoute la distance déjà parcourue pour atteindre le point $B$. 

On suppose donc que l'on part de $D$. On remplit à nouveau la ligne de $D$.

On remarque que à l'étape précédente, on aurait pu passer par $C$.

On regarde donc les possibilités offertes par $C$ que l'on compare à celles offertes par $D$ : finalement, la distance la plus courte est celle allant en $F$ depuis $D$.

On choisit donc $F$ et on regarde les possibilités de chemin depuis ce sommet. On complète la fin du tableau en suivant le même principe.

Afin d'obtenir le chemin le plus court, il ne s'agit pas d'écrire tous les sommets inscrits dans la colonne "choix", mais de remonter le raisonnement.

Ici, le chemin le plus court est $A-B-D-F-E-G$. 

 

$A$ $B$ $C$ $D$ $E$ $F$ $G$ Choix
X $3A$ $6A$ $5A$ $\infty$ $\infty$ $\infty$ $B$
    $5B$ $4B$ $\infty$ $\infty$ $\infty$ $D$
    $8D$   $10D$ $7D$ $\infty$ on choisit $C$ depuis $B$
    $5B$         $C$
        $10C$ $9C$ $14C$ on choisit $F$ depuis $D$
           $7D$    $F$
         $9F$    $11F$  $E$
             $10E$  $G$