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

paris13.nodes.csv Résumé

id	lat	lng
0	48.8263456	2.3614982
1	48.826185	2.3572626
2	48.8260749	2.3552177
3	48.8258123	2.3503781
4	48.8257548	2.3465866

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

arêtes

paris13.edges.csv Résumé

source	dest	longueur	type	vmax	nom
83	6609	6.27	tertiary	30	Rue Nationale
6609	4033	3.62	tertiary	30	Rue Nationale
4033	6611	5.72	tertiary	30	Rue Nationale
6611	2460	4.5	tertiary	30	Rue Nationale
10231	21	18.69	secondary	30	Avenue des Gobelins

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.

À 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.

Les fichiers que je donne sont réduits et simplifiés par exemple aux gros fichiers que l'on pourrait télécharger sur 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}$$