Plus court chemin
Les différents parcours vus permettent de trouver un chemin d'un sommet à un autre.
Mais la majorité du temps, on cherche le chemin le plus court, c'est-à-dire le chemin dont la somme des poids des arcs empruntés (la distance) est la plus petite.
Exemple : Quels graphes
La majorité du temps, la recherche du plus court chemin entre deux sommets se réalise sur un graphe orienté pondéré. Dans les autres cas cependant, l'algorithme restera toujours le même !
Méthode : Algorithme de Dijkstra
L'algorithme le plus populaire est celui d'Edsger Dijkstra, découvert en 1959 (voir son travail original en anglais, 3 pages).
On dispose d'un graphe, d'un sommet de départ D et d'un sommet d'arrivée A
Initialisation :
Tout au long de l'algorithme, on notera la distance entre D et chaque sommet du graphe.
Cette valeur est initialisée à ∞ sauf pour le sommet D où elle est initialisée à 0.
On enregistre également un sous-graphe intialement vide.
Itération :
Lors de chaque itération de l'algorithme, on choisit un sommet S qui ne fait pas partie du sous-graphe et dont la distance à D est minimale.
On ajoute ce sommet S au sous-graphe.
Depuis le sommet S, on met à jour la distance notée des voisins qui ne sont pas dans le sous-graphe :
on fait la somme de la distance de D à S (déjà connue) et de l'arc de S au voisin ;
si le résultat est inférieur à la distance entre D et le voisin, on la met à jour.
Finalisation :
L'algorithme termine lorsque le sommet A est dans le sous-graphe ou après épuisement des sommets disponibles.
Simulation :
De 1 | à 1 | à 2 | à 3 | à 4 | à 5 | à 6 |
|---|---|---|---|---|---|---|
Étape initiale | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
1 (0) | 7 | 9 | ∞ | ∞ | 14 | |
2 (71) | 9 | 22 | ∞ | 14 | ||
3 (91) | 20 | ∞ | 11 | |||
6 (113) | 20 | 20 | ||||
5 (206) |