Calcul de l’itinéraire :

Algorithme de Dijkstra.

C'est l'algorithme le plus efficace pour cette application.
Sur un exemple très simple, nous allons voir comment il opère.
Soit la carte ci-contre reproduite sous forme de graphe (donc le dessin n’est pas à l’échelle). Les ronds (nœuds du graphe) repérés par une lettre sont les villes (*), les traits les reliant (arêtes du graphe) sont les routes dont on donne une longueur en km (poids de l’arête) (**).

(*)Le graphe est également déterminé dans la ville intra-muros (rues, intersections, immeubles) mais pour simplifier le raisonnement, on ne prend ici que les villes et les routes.

(**) Comme poids, on peut aussi bien donner le temps de parcours (tenant compte des limitations de vitesse), le coût (tenant compte de la consommation d’essence et des péages) ou tout autre paramètre pour minimiser le temps, le coût du trajet ou n’importe quel autre critère.
Dans un premier temps, l’algorithme stocke tous les nœuds (A à F) dans une mémoire et il en retire un lorsque celui-ci voit toutes ses arêtes exploitées.
Ensuite, il effectue une opération récurente :
Boucle 1 : il prend en compte toutes les routes partant de A, compare leur poids et retient le plus faible :
AB = 240
AC = 185
AD = 180 = poids provisoirement le plus faible (mais n’atteint pas l’arrivée)
AE = 625
A est sorti de la mémoire. Il reste B, C, D, E, F dans la mémoire.

Boucle 2 : D devient un nouveau point de départ duquel on prend en compte toutes les routes qui en partent, soit DC et DF. On reprend tous les itinéraires déjà trouvés auxquels on ajoute les nouveaux et on compare leur poids :
AB = 240
AC = 185 = poids provisoirement le plus faible (mais n’atteint pas l’arrivée)
ADC = 250
ADF = 370
AE = 625
Il reste B, C, D, E, F dans la mémoire.
Suite de la récurence
Retour à l'accueil
Page précédente Page suivante