Chemin de poids minimal : Trajets dans le métro
Le programme
CitéFutée de la
RATP permet de trouver le chemin le plus
rapide entre deux points de la région parisienne par le
métro et le RER. Il fournit un bon exemple de recherche du plus
court chemin dans un graphe orienté valué. Le graphe est
orienté car les lignes 7 et 10 contiennent des boucles à
sens unique. En pratique, le graphe n'est pas tout à fait
connexe à cause du funiculaire de Montmartre dont on ne tiendra
pas compte.
L'objectif du TP est de réaliser une version
simplifiée de
CitéFutée.
Les temps de trajet entre deux
stations sont considérés comme constants et dans un
premier temps, les correspondances seront considérées
comme ne prenant pas de temps.
Un algorithme simple pour trouver le chemin de poids minimal entre deux
noeuds d'un graphe est le parcours en largeur utilisant une file de
priorité. Cet algorithme construit progressivement un
arbre dont la racine est la station de départ, et dont les
noeuds sont les stations accessibles en des temps inférieurs ou
égaux au temps nécessaire pour atteindre la station
d'arrivée.
1 Structures de données
1.1 Le graphe
Étant donnée la faible connectivité du graphe, la meilleure représentation
est un tableau dont chaque case correspond à une station et qui pointe sur la
liste des arêtes partant de cette station. Un numéro d'indice du tableau
correspondra donc de façon unique à une station. Inversement, il faudra faire
correspondre à chaque numéro le nom (ou les noms) de la station correspondante
et la liste de ses arêtes.
Chaque arête contient le numéro de la station d'arrivée, le temps de parcours
et le nom de la ligne.
Définir la structure de données
utilisée pour le stockage du graphe et déclarer la variable globale utilisée pour stocker le
graphe.
La file de priorité pourra être stockée comme une liste triée par temps de
parcours croissants. Les informations qui y sont
stockées sont les numéros des stations de départ
et d'arrivée, le temps d'accès depuis la station
d'origine et le nom de la ligne sur laquelle est cette arête. La fonction
d'insertion dans la file n'insère un nouvel élément que si elle ne trouve pas
d'autre élément dans la file avec la même station d'arrivée et un temps
d'accès plus court.
Écrire la structure de données utilisée
pour la file de priorité. Écrire ensuite la fonction d'insertion.
L'arbre construit par l'algorithme de parcours du graphe doit servir à
construire le chemin de poids minimal. L'algorithme s'arrêtera donc dès que
la station d'arrivée sera atteinte. Il faudra alors pouvoir rapidement
trouver quel est le chemin de l'arbre qui mène de la racine à la
station d'arrivée...
Définir une structure de données représentant l'arbre de parcours.
(Une solution possible...)
Écrire une fonction de parcours du graphe qui s'arrête dès que la
station d'arrivée est atteinte. Cette fonction, qui peut tenir en une
douzaine de lignes, sera appelée par une autre fonction qui fait les
initialisations puis imprime le chemin trouvé.
Quelques indications si vous en avez besoin...
Les données pour la génération du graphe se
trouvent dans le fichier metro.plan. Ce
fichier comporte des lignes de commentaire commencant par un
caractère '#', et des lignes dont un exemple est :
13:a:Champs Élysées, Clémenceau
Ces lignes comportent trois colonnes séparées par le
caractère ':'. La première colonne contient
le numéro de la ligne (c'est une chaîne de trois
caractères au plus), la deuxième indique une direction
('a' ou 'b', voire 'c',
'd'...) et la troisième contient
le nom de la station. Le fichier se lit de la façon suivante :
Il y a une arête entre deux stations lorsque ces
stations se succèdent sur deux lignes du fichier avec le
même numéro de ligne (du métro) et la même direction.
Écrire les fonctions de lecture du graphe et la fonction principale qui
demande une station de départ et une station d'arrivée et affiche le plus
court chemin entre les deux.
Indications
4 Extensions possibles
4.1 Prise en compte des temps de trajet
Le fichier metro+.plan fournit des renseignements
supplémentaires sur le métro, comme les horaires de premiers et derniers
métros ou des coordonnées de stations qui peuvent permettre d'estimer le temps
exact du trajet entre deux stations... À vous de l'exploiter !
4.2 Amélioration de l'algorithme
On peut améliorer l'algorithme de recherche du chemin de poids minimal
en construisant simultanément deux arbres de parcours, l'un partant du
point de départ, l'autre du point d'arrivée. L'algorithme termine dès que
les deux arbres se rencontrent.
4.3 Les temps de correspondance
Pour une recherche un peu plus réaliste, il faut tenir compte des temps
de correspondance. De fausses lignes appelées cor tiennent
compte des correspondances entre stations de nom différent. Il faut faire
quelque chose pour les correspondances avec le même nom de station...
4.4 La saisie des stations
Les noms de stations contiennent parfois des virgules, comme par exemple
dans
B:a:Luxembourg, École Normale Supérieure, ENS
Les parties entre virgules correspondent à des noms alternatifs pour les
stations. Il faut aussi rendre la saisie des stations plus intelligentes,
en autorisant par exemple de ne saisir qu'un préfixe de la station...