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 :
  1. Toutes les stations de départ de ses éléments sont dans l'arbre.
  2. 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