Terminale Economique et Sociale > Mathématiques > Graphes > Graphes

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

LES GRAPHES DIJKSTRA

Permalien

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

Les graphes 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&e

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.