7. Algorithme de Dijkstra

Dans le précédent chapitre, nous avons trouvé le moyen de se rendre d’un point A à un point B.
Ce n’était pas forcément le chemin le plus rapide. C’était le chemin le plus court car il comportait le moins de segments (trois segments). Mais supposons que vous ajoutiez des temps de trajet à ces segments. Vous voyez maintenant qu’il existe un chemin plus rapide.
Vous avez utilisé le parcours en largeur dans le précédent chapitre. L’algorithme de parcours en largeur trouve le chemin avec le moins de segments (le premier graphe montré ici). Et si vous vouliez plutôt le chemin le plus rapide (le deuxième graphe) ? Vous pouvez le faire rapidement avec un algorithme différent appelé algorithme de Dijkstra.
Voyons comment cela fonctionne avec ce graphe.
Chaque segment a un temps de trajet en minutes. Vous utiliserez l’algorithme de Dijkstra pour aller du départ à l’arrivée dans les plus brefs délais.Si vous exécutiez un parcours en largeur sur ce graphe, vous obtiendriez le plus court chemin.
Mais ce chemin prend 7 minutes. Voyons si vous pouvez trouver un chemin qui prenne moins de temps ! L’algorithme de Dijkstra comporte quatre étapes :
Trouvez le nœud « le moins coûteux ». C’est le nœud auquel vous pouvez accéder en un minimum de temps.
Mettez à jour les coûts des voisins de ce nœud. J’expliquerai ce que je veux dire par là sous peu.
Répétez jusqu’à ce que vous ayez fait cela pour chaque nœud du graphe.
Calculez le chemin final.Étape 1 …