Recherche du plus court chemin dans un graphe (algorithme de Dijkstra)

En 30 secondes

• L'algorithme de Dijkstra détermine le plus court chemin entre un sommet de départ et tous les autres sommets d'un graphe pondéré à poids positifs.
• À chaque étape : choisir le sommet non visité de distance provisoire minimale, la rendre définitive, mettre à jour les distances provisoires de ses voisins.
• Une distance provisoire peut être améliorée tant que son sommet n'est pas définitif ; une fois définitive, elle ne change plus.

Ce que tu sauras faire

• Décrire le principe de l'algorithme de Dijkstra (distances provisoires, sommet non visité de distance minimale).
• Dérouler l'algorithme de Dijkstra sur un graphe pondéré pour trouver le plus court chemin depuis un sommet de départ.
• Distinguer distance provisoire et distance définitive dans le déroulement de l'algorithme.

Les mots à connaître

Graphe

un ensemble de sommets reliés entre eux par des arêtes ou des arcs, représentant des relations entre des objets.

Sommet

chacun des éléments reliés entre eux dans un graphe, aussi appelé nœud.

Voisin

un sommet directement relié à un autre sommet par une arête ou un arc.

Le piège classique

Croire que la première distance provisoire trouvée pour un sommet est forcément la distance définitive : elle peut être améliorée tant que le sommet n'a pas été choisi comme sommet non visité de distance minimale.

L'astuce

Une distance provisoire n'est JAMAIS définitive tant que son sommet n'a pas été choisi comme sommet non visité de distance minimale.