Demander le programme

Repérage sur Terre

Méridiens et parallèles

Voici ci-dessous une schématisation de la Terre avec des lignes imaginaires.

Déplacer les curseurs pour obtenir les coordonnées approchées de votre ville.

( ; )

compléter les deux définitions suivantes en utilisant les mots méridiens et parallèles :

Les sont des cercles imaginaires situés dans des plans parallèles au plan de référence qui coupe la Terre en deux hémisphères Nord et Sud. Ces cercles sont repérés par rapport au grand cercle de référence : l'équateur

Les sont des demis grands cercles imaginaires reliant les pôles Nord et Sud. Ces cercles sont repérés par rapport au grand cercle de référence : le méridien de Greenwich

Longitudes et latitudes

Un point situé A sur un parallèle (demi-grand cercle noir sur l'image) donné est aussi l'image d'un point de l'équateur par une rotation, vers le Nord ou le Sud : l'angle $\phi$ de cette rotation est la latitude du parallèle.

Un méridien donné (celui rouge) et le méridien de Greenwich (demi-grand axe orange) déterminent, par rapport à l'axe Nord-Sud de la planète, un angle $\theta$ : c'est la longitude du méridien.

Les coordonnées géographiques sont exprimées soit :

L'Arc de Triomphe situé à Paris a pour coordonnées :

  • $N$ signifie que le lieu se situe dans l'hémisphère nord (au nord de l'équateur).

  • $E$ signifie que le lieu se situe à l'ouest du méridien de Greenwich (en gros à l'ouest par rapport à Londres).

  1. Aller sur le site https://www.coordonnees-gps.fr afin de vérifier les coordonnées de l'exemple précédent.

  2. Détermier l'altitude de l'Arc de Triomphe de Paris.

Tout point de la Terre est déterminé par ses coordonnées géographiques (la latitude et la longitude) et par son altitude (élévation par rapport au niveau de la mer).

  1. Sachant qu'il y a 60 minutes par degré, convertir en notation décimale cette latitude sexagésimale : $48° 20'$.

  2. Sachant qu'il y a 60 minutes par degré et 60 secondes par minutes, convertir en notation décimale cette longitude sexagésimale : $17° 49' 11"$.

  3. Aller sur le site https://www.coordonnees-gps.fr afin de vérifier la cohérence des coordonnées précédemment obtenues.

    Quelle ville de l'hémisphère Nord à l'Est de Greenwich se situe à ces coordonnées géographiques ?

  4. Copier_coller dans Edupython le code ci-dessous et remplacer les $...$ de la ligne 9 par une formule :

    def convertisseur_decimal(degre,minute,seconde):
        """ fonction qui :
            prend en argument trois nombres entiers,
            convertit une coordonnée donnée par sa valeur en degrés, minutes et secondes
            en sa valeur décimale,
            renvoie la valeur décimale de cette coordonnée.
        Exemple : convertisseur_decimal(17,49,11) renvoie 17.81972222222222"""
    
        angle = ... # ... à remplacer par votre code
    
        return angle
    	
  5. Code de déblocage de la correction :

  1. Sachant qu'il y a 60 minutes par degré, convertir en notation sexgesimale cette latitude décimale : $56.8$.

  2. Sachant qu'il y a 60 minutes par degré et 60 secondes par minutes, convertir en notation sexgesimale cette latitude décimale : $60.591389$.

  3. Aller sur le site https://www.coordonnees-gps.fr afin de vérifier la cohérence des coordonnées précédemment obtenues.

    Quelle ville de l'hémisphère Nord à l'Est de Greenwich se situe à ces coordonnées géographiques ?

  4. Copier_coller dans Edupython le code ci-dessous et remplacer les $...$ des lignes 11à 13 par une formule :

    from math import floor
    
    def convertisseur_sexagesimal(decimale):
        """ fonction qui :
            prend en argument un nombre flottant (à virgule),
            convertit une coordonnée donnée par sa valeur décimale
            en sa valeur hexadécimale : degre, minute, seconde (3 nombres entiers)
            renvoie le triplet formé de ces trois nombres.
        Exemple : convertisseur_decimal(60.59139) renvoie 60 , 35 , 29"""
    
        degre = ... # ... à remplacer par votre code
        minute = ... # ... à remplacer par votre code
        seconde = ... # ... à remplacer par votre code
    
        return degre,minute,seconde
        

    La fonction floor du module maths permet d'obtenir la partie entière d'un nombre réel, c'est à dire, pour un nombre positif, cette fonction enlève l'ensemble des nombres derrière la virgule.

    floor(3.14159) renvoie le nombre entier 3.

  5. Code de déblocage de la correction :

Pour les plus rapides :

Déplacer les curseurs de méridien et de parallèle afin de repérer sur la Terre les premières villes proposées.

Triangulation

Un trésor a été caché. 3 personnes se liguent pour le trouver : Bob, Olaf et Ramia. La personne qui a caché l'objet donne à chacun une information :

En utilisant le fichier Geogebra ci-dessous, trouver le lieu où est caché le trésor.

L'unité est le mètre et penser à utiliser l'onglet Cercle (centre-rayon)

Code de déblocage de la correction :

Compléter la propriété suivante :

Pour pouvoir se repérer dans un plan, il suffit de connaître distances par rapport à des points de repère.

Tout point de la Terre est déterminé par des coordonnées géographiques : latitude, longitude et altitude.

La latitude d'un lieu correspond à l'angle formé par la parallèle passant par ce lieu avec l'équateur.

La longitude d'un lieu correspond à l'angle formé par le méridien passant par ce lieu avec le méridien de Greenwich (proche de Londres).

Les systèmes de géolocalisation

Définition

Donner une définition du principe de la géolocalisation à l’aide de la vidéo accessible avec ce lien.

Code de déblocage de la correction :

Fonctionnement du GPS

Le but est de répondre aux questions suivantes à l'aide de deux vidéos.

L'ensemble des questions se trouve format modifiable ici ou en format .pdf ici.

    Visionner la vidéo accesible à cette adresse Puis répondre aux questions suivantes :

  1. Pourquoi la localisation peut être un peu imprécise ?

  2. Depuis quelle date fonctionne le GPS ?

  3. Quel objet est nécessaire au fonctionnement du GPS ?

  4. Quelles sont les deux principales informations contenues dans les messages envoyés par les satellites ?

  5. Comment est calculée par le récepteur la distance le séparant d'un satellite ?

  6. À quelle erreur de distance conduit une erreur de 0.001 secondes ?

  7. Quel facteur de précision gagne-t-on avec le système européen Galileo par rapport au système américain GPS ?

  8. En complément, visionner cette vidéo sur le système Galileo se trouvant à cette adresse, puis répondre aux questions suivantes :

  9. Quel est le principe de la trilatération ?

  10. Pourquoi un quatrième satellite est nécessaire ?

  11. Quelle est la précision de la synchronisation des satellites et du récepteur ?

  12. En plus des satellites, quelles autres infrastructures sont nécessaires ?

Code de déblocage de la correction :

La géolocalisation est la connaissance de la position sur Terre : elle permet d'avoir la latitude, la longitude et l'altitude.

Les systèmes américain GPS et européen Galiléo permettent la géolocalisation d'un récepteur à partir d'au moins quatre satellites.

Ils utilisent le décalage temporel entre l'heure d'émission par un satellite et celle de réception d'un message radio pour mesurer la distance approchée entre le récepteur et ces satellites. À partir de ces distances, le récepteur calcule ses coordonnées géographiques sur Terre (latitude, longitude et altitude) : c'est la trilatération.

Le quatrième satellite sert à corriger d'éventuels problèmes d'horloge : il y a synchronisation.

Les cartes numériques

Un exemple de carte numérique : GEOPORTAIL

Le Géoportail est un portail Web public permettant l'accès à des services de recherche et de visualisation de données géographiques ou géolocalisées.
Il a notamment pour but de publier les données géographiques de référence de l'ensemble du territoire français.
Vous pouvez vous rendre sur le site de Géoportail via le lien ci dessous :

accès à GEOPORTAIL

Géoportail est donc un portail accessible fourni par l’administration française.
Les informations sont directement issues des services administratifs français tels que le cadastre, les ponts et chaussées …

Quelle est votre ville ?

Code de déblocage de la correction :

Un autre : OPENSTREETMAP

Il existe depuis peu un portail opensource : OPENSTREETMAP.

accès direct à OPENSTREETMAP

Chacun peut accéder aux données d'OpenStreetMap, les modifier ou en ajouter.
Chacun peut utiliser les données d'OpenStreetMap pour des applications non commerciales.
Différentes applications pour des automobilistes, des cyclistes, des personnes handicapées à mobilité réduite, des skieurs, des randonneurs, ... ont été créées à partir de la base de données d'OpenStreetMap.

Pour les plus curieux

Un exemple d'application est par exemple le geocaching.

Ce jeu est une chasse au trésor. Des individus ont cachés dans différents endroits des objets et ont seulement donné le positionnement GPS de cette cache (voire quelques indices).
Plusieurs millions de tels "trésors" à trouver ont des informations disponibles sur le site officiel de geocaching.

  1. Aller sur le site officiel.

  2. Se connecter à l'aide :

    • de l'identifiant : SNTReims

    • du mot de passe : SNTReims

  3. Chercher les coordonnées GPS de l'objet nommé "La dame" caché à Vitry-le-François.

  4. Visualiser la carte qui apparait et qui sert à aider les personnes à trouver l'objet caché. D'où viennent les données ayant permis la réalisation de la carte affichée ?

Code de déblocage de la correction :

Les informations présentes sur les cartes d'OpenStreetMap peuvent être mises à jour ou corrigées par tout à chacun.

Pour les plus curieux

si vous regardez la carte du lycée, vous verrez que certains éléments manquent comme par exemple des arbres.

Si vous êtes intéressé.e, vous pouvez créer un compte sur ce site afin de compléter les manques observés.

Code de déblocage de la correction :

Il existe plusieurs sites Internet qui proposent des cartes numériques :

Le protocole NMEA

Nous avons maintenant des informations sur le fonctionnement physique d’un système de géolocalisation et avons vu la mise en pratique via Géoportail et OpenStreetMap.
Mais comment le logiciel de carte numérique connait-il les positions GPS ?

Rappel de ce qui a déjà été vu dans des vidéos précédentes

Votre récepteur GPS (Smartphone) reçoit des signaux depuis les satellites des différentes constellations de satellites servant à la géolocalisation (GPS (États-Unis), Galileo(Union Européenne), Glonass(Russie), Baidou(Chine)).
En traitant des données, il calcule votre position géographique : coordonnées et altitude. Le récepteur envoie ces informations sous forme de phrases électroniques appelées "trames" à différentes applications installées sur votre Smartphone.

Protocole NMEA

Afin que toutes les applications puissent utiliser ces "trames", il est nécessaire que le format de ces phrases suivent des normes fixes.

Compléter la définition suivante qui a déjà été vue dans le thème Internet :

En informatique, un ensemble de normes permettant à différents périphériques informatiques de dialoguer entre eux en réseau est appelé un .

Pour les trames issues de récepteurs GPS, les normes du protocole sont définies et contrôlées par la National Marine Electronics Association (NMEA), association américaine de fabricants d'appareils électroniques maritimes. Pour cette raison, on parle de protocole NMEA.

Il y a deux Normes NMEA :

La seule norme au programme de SNT est celle NMEA 0183 car cette trame est lisible.

Une trame NMEA (sous-entendu NMEA 0183) est donc une suite de caractères contenant des informations de géolocalisation comme :

Utilisation d'une trame NMEA

Au vu de vos compétences informatiques poussées, vous avez été recruté.e.s comme membre du contre-espionnage français : félicitations !
Vous avez installé une application pirate dans le Smartphone d'une personne que vous avez à surveiller. Cette application vous renvoie à heures fixes les trames NMEA du récepteur GPS du smartphone espionné.

Voici la trame transmise :

$$\$GPGGA,104022.313,4851.4956,N,00217.6699,E,1,05,3.2,323.1,M,,,,0000*0E$$

Vous avez deux questions auxquelles vous devez répondre pour la surveillance établie :

  1. à quelle heure le récepteur a-t-il envoyé cette trame ?

  2. Où peut donc se trouver la personne que vous surveillez ?

Pour déchiffrer la trame NMEA et répondre à ces questions, vous avez utiliser les compléments d'informations du petit manuel de l'espion donné votre service de contre-espionnage :

Complément 1 : sur les deux premiers caractères après le symbole $\$$ :

Les deux premiers caractères suivant $\$$ permettent d'identifier les satellites qui sont à l'origine des signaux reçus. Les principaux préfixes sont :

  • BD ou GB - Beidou,

  • GA - Galileo,

  • GP - GPS,

  • GL - GLONASS.

Complément 2 issu du site de Wikipédia :

Complément 3 sur le calcul de la valeur de la latitude :

Le troisième élément de la trame NMEA donne la valeur de la latitude écrite de manière compliquée. Pour retrouver la coordonnées en DMS (Degré, Minutes et Secondes), sachez que :

  • les deux premiers chiffres avant le point correspondent au nombre de minutes,

  • les chiffres qui précédent les deux premiers chiffres avant le point correspondent au nombre de degré,

  • les nombres derrière la virgule permettent d'obtenir les secondes par proportionnalité.

  • Dans $\$GPGGA,092750.000,5732.4296,N,00444.0390,O,1,08,1.4,15.8,M,,,,0000*35$ :

    La latitude est donnée par $57 \color{red}{32} \color{blue}{.4296}$ ; La latitude est donc de :

    • $57$ degrés

    • $\color{red}{32}$ minutes

    • $\color{blue}{.4296}$ minute forment 25.776 secondes car $0.4296\times 60=25.776$.

    Ainsi, la latitude est de 57°32'25.776".

  1. à quelle heure le récepteur a-t-il envoyé cette trame ?

    Code de déblocage de la correction :

  2. Où peut donc se trouver la personne que vous surveillez ?

    Code de déblocage de la correction :

  1. Voici un exemple de trame GPS, quelle est la ville indiquée par cette trame :

  2. Voici un autre exemple de trame GPS, quelle est la ville indiquée par cette trame :


  3. Voici un autre exemple de trame GPS, quelle est la ville indiquée par cette trame :


Determinez le lieu ou la photo a été prise :





La liste des données Exif (Exchangeable Image file format) intégrées par vos appareils photos numériques regroupe une foule d'informations parmi lesquelles :

Certains sites web comme : http://metapicz.com/ ou https://www.metadata2go.com/ permettent d’obtenir tout un ensemble de données sur la photo.


Utilisation d'un code Python pour automatiser l'étude d'une trame NMEA

Comme en réalité, votre récepteur envoie de nombreuses trames chaque minute, il est préférable en tant qu'espion que vous automatisiez la localisation de la personne suivie directement sur une carte.

Code à comprendre

  1. Voici ci-dessous un code à saisir (par copie ou par saisie) sur EduPtyhon (il est inuile de saisir les commentaires commençant par le symbole dièse #) :

    import webbrowser # bibliothèque permet d'interagir avec le navigateur
    
    zoom='16'       # Faire des essais avec différentes valeurs pour comprendre le rôle de ce paramètre
    latitude=55.75025 
    longitude=37.6205 
    
    webbrowser.open("https://www.openstreetmap.org/#map=" + zoom + "/" + str ( latitude ) + "/" + str ( longitude))
    	
  2. Saisir puis exécuter le script précédent.
    Que se passe-t-il au moment de l'exécution ?

  3. Que remarquez-vous quand aux éléments apparaissant dans l'URL ?

  4. Quelle ville est représentée ?

Code de déblocage de la correction :

Code à comprendre

  1. Voici ci-dessous un code à saisir (par copie ou par saisie) sur EduPtyhon (il est inuile de saisir les commentaires commençant par le symbole dièse #) :

    import webbrowser # bibliothèque permet d'interagir avec le navigateur
    
    zoom='16'       # Faire des essais avec différentes valeurs pour comprendre le rôle de ce paramètre
    latitude=55.75025 
    longitude=37.6205 
    
    webbrowser.open("https://www.openstreetmap.org/#map=" + zoom + "/" + str ( latitude ) + "/" + str ( longitude))
    	
  2. Saisir puis exécuter le script précédent.
    Que se passe-t-il au moment de l'exécution ?

  3. Que remarquez-vous quand aux éléments apparaissant dans l'URL ?

  4. Quelle ville est représentée ?

Code de déblocage de la correction :

Premières utilisations du script

Voici différentes trames.

Pour chacune des trames ci-dessous, calculer à la main la latitude et la longitude en degrés décimaux, puis utiliser le programme Python de l'exercice précédent pour localiser la ville et l'État correspondant à la trame.

  1. Trame 1 : $\$GAGGA,145923.12,5230.9720,N,01322.6620,E,1,08,0.21,41,M,,,,0000*0E$.

  2. Trame 2 : $\$GPGGA,085416.23,4850.8956,N,06732.9298,O,1,06,2.35,1,M,,,,0000*0E$.

  3. Trame 3 : $\$GPGGA,194701.45,2612.3990,S,02802.6016,E,1,06,2.35,1,M,,,,0000*0E$.

Code de déblocage de la correction :

Automatiser le programme en Python

La valeur de la latitude, sans le signe, est présente dans une trame NMEA 0183 en troisième position.

Il est possible d'extraire automatiquement par un programme cette information pour la transformer en un résultat en degrés décimaux.

Voici ci dessous le script en python d'une fonction latitude qui renvoie la latitude (sans le signe et en degrés décimaux) d'un lieu à partir d'une trame NMEA 0183.
Le script est téléchargeable ici.

  1. Lire les commentaires (précédés d'un symbole #) afin de comprendre comment fonctionne cette fonction.

  2. Pour obtenir la fonction longitude qui renvoie la longitude (sans le signe et en degrés décimaux) d'un lieu à partir d'une trame NMEA 0183, il suffit de reprendre le code de la fonction latitude avec quelques modifications.

    1. Quelles sont les modifications à faire pour avoir une telle fonction longitude ?

    2. Programmer cette fonction longitude sur EduPython puis tester cette fonction, par exemple avec la trame : $\$GPGGA,194701.45,2612.3990,S,02802.6016,E,1,06,2.35,1,M,,,,0000*0E$ :
      Il suffit dans la console de lancer successivement les deux lignes suivantes :

      
      trame = "$GPGGA,194701.45,2612.3990,S,02802.6016,E,1,06,2.35,1,M,,,,0000*0E"
      longitude(trame)
      

      Normalement, l'affichage obtenu doit être : 28.04336

  3. On a déjà vu que la latitude d'un lieu est en fait un nombre avec un signe :

    • si le lieu est situé dans l'hémisphère nord, alors la latitude est positive,

    • sinon la latitude est négative.

    Dans une trame NMEA 0183, la position par l'équateur est donnée par 1 lettre :

    • N : si le lieu est situé dans l'hémisphère nord,

    • S : si le lieu est situé dans l'hémisphère sud.

    Voici ci-dessous le script de la fonction signe_latitude.
    Cette fonction fera appel à la fonction latitude étudiée précédemment pour renvoyer la latitude, avec son signe, du lieu correspond à la trame entrée comme paramètre.

    Compléter la ligne 8 : if .......... afin que cette fonction soit opérante.

    • n'oubliez pas de mettre des guillemets " pour définir une chaîne de caractères,

    • ne pas confondre l'affectation avec = et la comparaison avec ==.

    def signe_latitude(trame):
        """fonction qui renvoie la latitude du lieu avec son signe en degré décimal
        (positive si dans l'hémisphère Nord, négative sinon)
        à partir de la trame NMEA 0183 entrée comme paramètre"""
    
        liste_information=trame.split(",")  # liste des éléments composants la trame
    
        if ........................................................................
            return(latitude(trame))
        else:
            return(-latitude(trame))
    
  4. On a déjà vu que la longitude d'un lieu est en fait un nombre avec un signe :

    • si le lieu est situé à l'est du méridien de Greenwich, alors la longitude est positive,

    • sinon la longitude est négative.

    Dans une trame NMEA 0183, la position par l'équateur est donnée par 1 lettre :

    • O : si le lieu est situé à l'ouest du méridien de Greenwich,

    • E : si le lieu est ssitué à l'est du méridien de Greenwich.

    Modifier le code de la question précédente donnant la fonction signe_latitude pour obtenir une fonction signe_longitude qui renvoie la longitude, avec son signe, du lieu correspond à la trame entrée comme paramètre.

  5. Pour obtenir un script complet qui affiche les coordonnées du lieu en degrés décimaux et permet la visualisation sur OpenStreetMap, il suffit de rassembler les différentes fonctions précédentes dans un même programme en suivant la structure du code apparaissant ci-dessous :

    1. Le faire.

    2. Tester votre programme en l'exécutant avec la trame suivante : $\$GPGGA,194701.45,2612.3990,S,02802.6016,E,1,06,2.35,1,M,,,,0000*0E$
      Il doit faire faire afficher :

      • latitude du lieu en degrés décimaux : -26.20665

      • longitude du lieu en degrés décimaux : 28.04336

      • et doit faire apparaître l'image ci-dessous dans le navigateur :

  6. Pour utiliser le script, il suffit de remplacer la trame de la ligne 5 en remplaçant la chaîne de caractères entre guillemets " par la trame voulue.

Code de déblocage de la correction :

Les informations de géolocalisation peuvent être regroupés dans un message composés de caractère respectant un certain nombre de protocoles (= règles) : c'est la trame NMEA. La trame NMEA 0183 est créée par le récepteur GPS d'un objet comme un smartphone à partir des informations issues de satellites. Les différentes informations contenues sont séparées par une virgule.

Il est possible de décoder une trame NMEA 0183 pour obtenir en particulier les informations suivantes :

Sauf temporairement en cas d'un service rendu qui vous serez nécessaire, refusez de partager votre géolocalisation afin de protéger vos données personnelles.

Calculs d'itineraires

Organisation d'un voyage

Vous avez prévu de vous rendre en voiture à Gibraltar (au sud de l'Espagne). Vous prenez en partant un.e ami.e à Vitry-le François. Vous désirez savoir quel chemin vous sera le plus rapide entre Vitry-le François et Gibraltar.

Il existe différent sites Web comme Mappy, Via Michelin, OpenStreetMap et Google Maps, qui permettent de conseiller plusieurs itinéraires selon des critères prédéfinis par l'utilisateur.

    1. Aller sur le site Mappy.

    2. Gérer correctement les cookies (en faisant en sorte de refuser le maximum de cookies !) et la géolocalisation (en la refusant !).

    3. Prendre une copie de l'image du trajet le plus rapide proposé par ce site.
      Garder en note le temps et la distance annoncés par ce site.

  1. Aller sur le site viamichelin pour effectuer la même recherche.

  2. Aller sur le site openstreetmap pour effectuer la même recherche.

  3. Aller sur le site Googlemap pour effectuer la même recherche.

    1. Combien de trajets différents obtenez-vous ?

    2. Pour un même trajet proposé par deux sites différents, le temps et la distance sont-ils les mêmes ?

    3. Quel écart de temps entre le court et le plus long obtenu entre ces 4 sites ?

Code de déblocage de la correction :

Algorithme de Dijkstra

Tous les sites précédents utilisent différents algorithme pour déterminer le chemin le plus court entre deux points, à partir d'une base de données.

Un des plus fameux et simple est l'algorithme de Dijkstra.

Modélisation

Tout trajet (en voiture) entre des villes peut être modélisé par un ensemble appelé graphe pondéré formé de noeuds (=points), d'arêtes (=traits) et de poids (= nombres réels positifs) :

Voici une carte de villages proche de Vitry-le-François :

Nous ne considérons pour simplifier que les villages suivant :

On peut modéliser les différents villages par des noeuds et les routes les plus courtes existantes entre deux villages par des arêtes, en y précisant leur longueur.
On obtient un graphe pondéré comme celui ci-dessous :

Attention ! Dans ce graphe, les positions géographiques de chaque village ne comptent plus, seules les routes directes et leur longueur sont prises en compte !

Pour simplifier les notations, une lettre est associée à chaque village :

D'où le graphe suivant qui est équivalent au précédent mais avec une disposition différente des villages :

Représenter ci-dessous le graphe pondéré modélisant seulement les trajets entre les villages de :

Code de déblocage de la correction :

Algorithme de Dijkstra

L'exercice de cette partie sert à découvrir l'Algorithme de Dijkstra.

Si vous avez des difficultés, n'hésitez pas à visionner la vidéo intégrée ci-dessous qui a été réalisée par Yves Monka pour son site.

Intérêt de l'algorithme de Dijkstra:
Il permet de connaître le plus court chemin entre un sommet choisi et chacun des autres sommets.

Énoncé simplifié du début de l'algorithme:
On part du village de départ et on ne s'intéresse qu'aux villages directement accessibles. Au cours de chaque itération, on choisit, parmi les villages encore atteignable, le village à la distance minimale de la plus proche voisine ; on rajoute ce village avec la distance minimale obtenue à l'ensemble des résultats et on interdit d'y retourner.

Le but de cet exercice est de découvrir comment fonctionne l'algorithme de Dijkstra sur le cas de l'exemple précédent ; cet algorithme va nous permettre de déterminer le chemin le plus court entre les villages de Saint-Amand-Sur-Fion (A) et Heiltz-l'Évèque (H).

Rappel du graphe permettant de visualiser les données :

Voici un tableau qui a été en partie rempli par cet algorithme de Dijkstra :

Ce tableau incomplet peut être télécharger en version .docx ou en version libre .odt.

Pour comprendre l'algorithme, regardez la vidéo proposée ci-dessus ou lisez les explications suivantes :

Ligne 1 :

On part de A, le village de départ :

La première ligne correspond aux différents sommets (= villages) du graphe.

Ligne 2 :

On part de A, le village de départ :

Ligne 3 :

Pour la troisième ligne :

Étape 1 : on note la longueur du chemin de A à chacun des sommets adjacent non encore interdit.

Étape 2 : on garde le sommet ayant le poids le plus petit :

Étape 3 : on garde en mémoire le village le plus proche actuellement trouvé et sa distance :

Ligne 4 :

On recommence comme pour la troisième ligne mais en partant cette fois de S avec le poids 2.4.

Étape 1 : on note la longueur du chemin de S à chacun des sommets adjacent non déjà traité (on exclut donc A et S). On ajoute la distance pour aller déjà à S. Deux cas alors :

Étape 2 : on garde le sommet au poids le plus petit :

Étape 3 : on garde en mémoire le village le plus proche actuellement trouvé et sa distance.

Lignes suivantes :

Procéder de même qu'aux lignes 3 ou 4 jusqu'à ce que tous les sommets soient traités.

Recopier et compléter le tableau évoqué à l'exercice précédent, reproduit ci-dessous, en répétant la démarche expliquée dans la vidéo ci-dessus ou dans l'exercice précédent.

Code de déblocage de la correction :

Fin de l'algorithme :

Il suffit de remonter dans le tableau à partir du sommet correspond au village visé (ici H) pour trouver le chemin (à rebours) qui part du sommet de départ (ici A).

Pour comprendre la fin de l'algorithme de Dijkstra, n'hésitez pas à regarder la vidéo proposée ci-dessus à partir de la 9ème minute.

Appliquer la fin de l'algorithme pour trouver le chemin le plus court ainsi que la distance totale pour aller de Saint-Amand-Sur-Fion (A) à Heiltz-l'Évèque (H).

Code de déblocage de la correction :

Determinez le plus cours chemins (algorithme de Dijsktra) :


  1. Quel est le chemin le plus court ?

  2. Dans quel ordre ont été complétées les distances de chaque ville ?

Algorithme de Dijkstra programmé en Python

Programme Python

Dans la partie précédente, vous avez étudié à la main quel était le trajet le plus court entre les villages de Saint-Amand-Sur-Fion (A) et Heiltz-l'Évèque (H) en ne considérant que les chemins existant entre les villages suivant :

Vous allez désormais pouvoir vérifier votre résultat grâce à un programme en python qui :

Voici ci-dessous un programme en langage Python :

# importation des différentes bibliothèques utiles ici
import networkx as nx               # pour gérer les graphes
import numpy as np
import matplotlib.pyplot as plt     # pour le tracé du graphe
import pylab                        # pour le tracé du graphe

# création d'un graphe vide
G = nx.Graph()

# ajout au graphe des différents sommets, arêtes et des poids
G.add_edges_from([('U','T')], weight=4.2)
G.add_edges_from([('U','L')], weight=4.8)
G.add_edges_from([('U','V')], weight=4.2)
G.add_edges_from([('T','V')], weight=3.6)
G.add_edges_from([('H','V')], weight=3.8)
G.add_edges_from([('C','H')], weight=6.4)
G.add_edges_from([('T','C')], weight=3.4)
G.add_edges_from([('C','V')], weight=4.4)
G.add_edges_from([('C','S')], weight=5.3)
G.add_edges_from([('A','S')], weight=2.4)
G.add_edges_from([('A','L')], weight=3.0)
G.add_edges_from([('L','S')], weight=2.5)

# création d'un dictionnaire utilisé ensuite pour que les arètes s'affichent avec leur poids.
edge_labels=dict([((u,v,),d['weight'])
                 for u,v,d in G.edges(data=True)])

pos=nx.circular_layout(G)
# commande pour faire des arêtes avec indication de poids
# commande qui utilise pylab
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
#commande pour tracer le graphe
nx.draw(G,pos, node_color = 'yellow',with_labels=True, node_size=1500,edge_color='black',edge_cmap=plt.cm.Reds)
pylab.show()

# affichage du trajet le plus court pour le graphe G entre les deux derniers paramètres, ici 'A' et 'H'
print("Le trajet le plus court mesure",(nx.dijkstra_path_length(G,'A','H')),"kilomètres.")
print("Le trajet le plus court passe par les villages successifs : ",(nx.dijkstra_path(G,'A','H')))

Exécuter le script précédent sur EduPython et comparer les résultats obtenus (graphe et chemin le plus court) avec ceux obtenus précédemment.

Si votre Edupython n'est pas fonctionnel, vous pouvez utiliser capytale2 en :

  1. vous connectant à ce site : https://capytale2.ac-paris.fr,

  2. vous identifiant seulement grâce à l'ENT de la Région Grand-Est :

  3. cliquant sur Mes activités :

  4. En saisissant dans ce code : b4d4-3683

Normalement :

  1. après un petit temps de calcul, une fenêtre avec un graphique modélisant la situation apparaît. (vous devez voir un graphe très proche de celui-ci.)

  2. une fois que vous fermez la fenêtre précédente, le programme se termine en affichant la longueur du trajet le plus court, puis la liste des villages à traverser pour réaliser ce trajet le plus court.

Code de déblocage de la correction :

Vous pouvez retrouver cet exercice sur capytale2 avec ce code à y saisir : b5a1-3685

Vous allez modifier le script précédent afin de l'adapter à différents changements.

  1. Suite à une tempête, des arbres se sont abattus sur la route menant de Changy (C) à Heiltz-l'Évèque (H) : elle est désormais fermée. Il vous faut modifier le programme précédent afin que vous obteniez le nouveau chemin le plus court entre les villages de Saint-Amand-Sur-Fion (A) et Heiltz-l'Évèque (H)

    1. Comment modifiez-vous le programme précédent pour prendre en compte la fermeture de la route mentionnée ?

      Code de déblocage de la correction :

    2. Quel chemin obtenez-vous désormais ?

    3. Quelle est la distance désormais à parcourir ?

    4. Code de déblocage de la correction :

  2. Une fois à Heiltz-l'Évèque (H), vous désirez repartir vers Saint-Lumier-en-Champagne (S). Il vous faut modifier le programme précédent afin que vous obteniez le nouveau chemin le plus court entre les villages de Heiltz-l'Évèque (H) à Saint-Lumier-en-Champagne (S). (La route entre Heiltz-l'Évèque (H) et Changy (C) est toujours coupée)

    1. Comment modifiez-vous le programme précédent pour cela ?

    2. Quel chemin obtenez-vous désormais ?

    3. Quelle est la distance désormais à parcourir ?

    Code de déblocage de la correction :

Application concrète

Vous pouvez retrouver cet exercice sur capytale2 avec ce code à y saisir :

Votre meilleur ami, BGdu52, habite à Saint-Dizier. Vous avez décidé d'aller le retrouver dans sa belle ville puis qu'ensemble vous partirez en bus à la plage de Sainte Marie Du Lac, au bord du Lac du Der.

Pour la préparation de ce grand jour, vous avez pour charge de trouver le trajet de bus optimal pour vous deux. Vous avez trouvé sur Internet les informations résumées dans le tableau suivant :

Le tableau suivant donne les liaisons possibles avec leur temps de parcours et leur distances :

Liaison Distance Temps
Saint-Dizier/Hallignicourt 6km 9 min
Hallignicourt/Ambrières 4 km 6 min
Ambrières/Landricourt 7 km 9 min
Landricourt/Sainte Marie du Lac 8km 14 min
Saint-Dizier/Valcourt 4,5 km 7min
Valcourt/Eclaron 5 km 7 min
Eclaron/Sainte-Livière 3,5km 4 min
Sainte-Livière/Sainte Marie Du lac 8,9 km 13 min
Laneuville au pont/Ambrières 1,8 km 2 min

Nous avons réalisé un script Python qui permet de construire un graphe et de déterminer le plus court chemin avec l'algorithme de Dijsktra :

  1. Vous allez reprendre le le script de l'algorithme de Dijkstra en faisant en sorte que :

    • les lettres soient remplacées par le nom des communes (par exemple, en remplaçant 'A' par "Saint-Dizier")

    • en prenant dans un premier temps comme poids d'arête les distances.

    Écrire un script comme demandé ci-dessus par modification du script de l'algorithme de Dijkstra.

    Code de déblocage de la correction :

  2. Lancez le script python puis vérifier que l'image du graphe obtenu est similaire à celle-ci :

  3. Quel est le trajet à effectuer en bus si l'on veut parcourir la distance la plus faible entre Saint-Dizier et Sainte Marie du Lac ? Préciser cette distance minimale.

    Code de déblocage de la correction :

  4. Modifier le programme précédent afin de connaître le temps en bus minimal pour rejoindre Sainte Marie du Lac depuis Saint-Dizier.
    Quel est le trajet de temps minimal, c'est-à-dire le plus rapide ? Quel est ce temps minimal ?

  5. Code de déblocage de la correction :

La recherche du meilleur itinéraire (en temps ou en longueur) d'un point à un autre peut être obtenue à l'aide d'algorithmes ; celui de Dijkstra en est un d'entre eux. Il fonctionne grâce à une représentation de la situation grçace à un graphe.

Escape game de moins d'une heure.

Le monde est en danger ! Seul.e.s vous pouvez peut-être le sauver !

Êtes-vous prêt.e.s à partir pour cette mission contaminante ?
Si oui, saisissez votre code secret vous permettant d'accéder aux informations secrètes de cette nouvelle mission.

Entrez votre code secret si vous accepter de partir dans une nouvelle mission :

Escape game de plus d'une heure.

Une bombe a peut-être été posée ! Des vies sont surement en jeu !

Êtes-vous prêt.e.s à partir pour cette mission explosive ?
Si oui, saisissez votre code secret vous permettant d'accéder aux informations secrètes de cette nouvelle mission.

Entrez votre code secret si vous accepter de partir dans une nouvelle mission :

Licence Creative Commons
Les différents auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International