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 d'un plus court chemin du sommet A au sommet F
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 !
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.
Exemple
Animation montrant une exécution de l'algorithme de Dijkstra
| 1 | 2 | 3 | 4 | 5 | 6 | On garde |
|---|---|---|---|---|---|---|
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | 1 |
| · | 71 | 91 | ∞ | ∞ | 141 | 2 |
| · | · | 172 | 222 | ∞ | ∞ | 3 |
| · | · | · | 203 | ∞ | 113 | 6 |
| · | · | · | 206 | · | 4 | |
| · | · | · | · | 264 | · | 5 |