GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Plus court chemin sur une carte ======

===== Problème posé =====

Vous disposez de données décrivant les routes du 13e arrondissement de Paris.

On souhaite se donner un point de départ, un point d'arrivée et calculer un plus court chemin respectant les routes indiquées dans les fichiers.

Bien qu'on se soit limité au 13e arrondissement, les données sont volumineuses : plus de 10 000 nœuds et autant d'arêtes entre ces nœuds.


===== Les données =====

Vous disposez de deux fichiers.

=== Nœuds ===

{{ :nsi:tds:graphes:paris13.nodes.csv |}} //Résumé//

<csv :nsi:tds:graphes:paris13.nodes.csv maxlines=5></csv>

Ce fichier donne des nœuds correspondant à des points sur la carte. Cette nœud sont identifié par un entier ''id''.

=== arêtes ===

{{ :nsi:tds:graphes:paris13.edges.csv |}} //Résumé//

<csv :nsi:tds:graphes:paris13.edges.csv maxlines=5></csv>

Il s'agit de routes.

  * ''source'' et ''dest'' correspondent à ''id'' dans l'autre fichier.
  * Les longueurs sont données en mètres.
  * ''deuxsens = 1'' quand la voie est à double sens, ''0'' pour un sens unique.

<WRAP box>
===== À vous =====

Il faudra 
  * lire le contenu des fichiers,
  * construire un graphe avec ces données,
  * demander à l'utilisateur un point de départ et un point d'arrivée,
  * chercher le plus court chemin entre ces deux points -- algorithme de Dijkstra
  * Afficher ce chemin par exemple en donnant la liste des voies à emprunter, en précisant les distances.

</WRAP>

<WRAP tip>Les fichiers que je donne sont réduits et simplifiés par exemple aux gros fichiers que l'on pourrait télécharger sur [[https://www.openstreetmap.fr/|openstreetmap]] //c'est d'ailleurs là que j'ai pris mes données//. Vous ne pourrez donc pas indiquer les points de départ et d'arrivée comme vous le feriez sur une application comme GoogleMap. Une solution est de préciser une localisation GPS et de choisir le nœud le plus proche.

Pour cela, vous pouvez utiliser le calcul de distance en mètres entre deux points de latitude et longitude connues (en degrés):

$$distance = 111\,120 \cdot \sqrt{\left[(lng_1 - lng_2)\cdot\cos\left(\frac{lat_1 + lat_2}{360}\cdot\pi\right) \right]^2 + \left[lat_1 - lat_2\right]^2}$$
</WRAP>