Indications pour l'algorithme de parcours du graphe
La fonction de parcours du graphe prend en entrée la station d'arrivée et
la file de priorité initiale. La file de priorité a les propriétés suivantes :
- Toutes les stations de départ de ses éléments sont dans l'arbre.
- La première station d'arrivée de ses éléments qui n'est pas dans l'arbre
est la plus proche de toutes les stations qui ne sont pas dans l'arbre du
point de départ.
Il suffit donc de supprimer tous les éléments en tête de file dont la
station d'arrivée est dans l'arbre. Puis, on ajoute dans l'arbre l'arête
correspondant à l'élément de tête. On rajoute dans la file (en prenant garde
de la garder triée par temps croissant, voir
plus haut) les arêtes partant de la station rajoutée
et menant à une station qui n'est pas dans l'arbre. Attention, le nouveau temps
dans la file doit être le temps total pour venir de la station de départ
(celle du début). Enfin, on supprime l'élément de tête de la file, et on
itère.
Retour au sujet