C++ Application de l'algorithme de Dikjstra sur un graphe

1. Objectifs Utiliser une bibliothèque normalisée (la «STL»). Implémenter une représentation de graphe. Implémenter un algorithme de recherche de chemin dans un graphe. 2. Introduction Vous devez écrire un programme C++ nommé tp3 qui calcule des chemins de distance minimale entre des lieux dans une carte. Votre programme doit pouvoir être lancé en ligne de commande avec la syntaxe suivante : ./tp3 [nomfichier] où nomfichier est optionnel. Si nomfichier est spécifié, alors votre programme doit lire dans nomfichier au moyen d'un flux de lecture C++ std::ifstream. Sinon, votre programme doit lire dans l'entrée standard (stdin) au moyen du flux d'entrée C++ std::cin. Les chemins calculés doivent être écrit dans la sortie standard (stdout) à l'aide du flux de sortie C++ std::cout. Un squelette de départ est disponible dans tp3.zip. 3. Formats d'entrée et de sortie 3.1 Entrée L'entrée est constituée de : Une liste* de lieux. Un lieu est spécifié par un nom et par une coordonnée de la forme (x,y) où x et y sont des réels. Trois tirets (---) de séparation. Une liste* de routes. Une route est spécifiée par une paire de lieux séparés par «->» (sens unique) ou par «» (deux directions). À noter que la direction «>, il y a au moins un espace blanc (espace, tabulation ou retour de ligne) après chaque nom de lieu. Voici un exemple d'entrée ([login to view URL]) : a (5.0,40.0) b (45.0,10.0) c (60.0,40.0) d (100.0,25.0) e (100.0,62.0) f (120.0,40.0) --- a -> b b -> c c -> a c d c e d f e f --- a f f b Et la carte correspondante : 3.2 Hypothèses On suppose que les routes sont droites. Ainsi, la longueur d'une route est la distance euclidienne séparant les deux lieux qu'elle relit. Par exemple, la longueur de la route l0->l1 est de 50 unités. Dans les tests, le nombre de requêtes sera inférieur au carré du nombre de lieux (n2). Cela devrait vous donner un indice quant à l'algorithme à utiliser (ou à ne pas utiliser). Il peut y avoir plusieurs requêtes à partir d'un même lieu d'origine. Dans ce cas, ces requêtes peuvent être consécutives. 3.3 Sortie Votre programme doit écrire en sortie les chemins calculés. Un chemin est spécifié par la liste des lieux à emprunter, séparés par un espace, et dans l'ordre du parcours, pour de se rendre de l'origine à la destination. S'il n'existe pas de chemin entre l'origine et la destination, il faut afficher "!" (voir [login to view URL]). Chaque chemin est suivi d'un saut de ligne (\n). Voici un exemple de sortie ([login to view URL]) : a b c d f f d c a b 4. Contraintes 4.1 Librairies permises Utiliser, autant que possible, les conteneurs de la librairie standard de C++ (Standard Template Library). Cette contrainte vise à mettre en pratique l'utilisation d'une bibliothèque normalisée. Évidemment, vous pouvez créer vos propres structures si cela s'avère nécessaire. Cela est nécessaire lors qu'une structurée requise n'est pas offert par la STL, ou lorsque la structure offerte dans la STL ne conviennent pas à vos besoins précis. Par exemple, vous devrez fort probablement créer une classe Graphe ou Carte. Des tests sont disponibles dans tp3-tests.zip. Les résultats attendus sont disponibles pour les 10 premiers tests.