Lycée   >   Seconde   >   SNT   >   Carte routable et calcul d'un itinéraire

Carte routable et calcul d'un itinéraire

  • Fiche de cours
  • Quiz
  • Profs en ligne
Objectifs
  • Maitriser le vocabulaire basique sur les graphes.
  • Représenter un calcul d’itinéraire comme un problème sur un graphe.
  • Comprendre le fonctionnement de parcours d’un graphe par l’algorithme de Dijkstra.
Points clés
  • Une carte qui permet le calcul d’itinéraires est appelé carte routable.
  • On peut représenter un calcul d’itinéraire en le modélisant par un graphe (mathématique).
  • Un graphe est constitué de sommets (qui représentent généralement les villes) et d'arêtes pondérées (qui représentent l’information de parcours).
Pour bien comprendre

Les caractéristiques d’une carte numérique (notamment les entités lignes et les données attributaires)

1. Carte routable
Une carte est routable si elle permet le calcul d’itinéraires à partir des informations qu’elle contient.
Exemples d’informations d’une carte routable :
  • le type de voie (autoroute, route nationale, etc.)
  • la vitesse maximale autorisée (50, 80, 110, etc.)
  • le sens de circulation
  • les routes à péage
  • le type d’usagers (piéton, vélo, voiture, etc.)

Toutes les cartes utilisées par nos récepteurs GPS sont routables.

2. Calcul d'itinéraire
a. Généralités
Itinéraire et graphe
Un itinéraire est une route à suivre pour aller d’un lieu à un autre selon un ou plusieurs critères (le plus rapide, le plus court, le moins cher, etc.).

Un itinéraire peut être schématisé par un graphe.

Un graphe est une représentation d’un ensemble de relations. Il est composé d’un ensemble de sommets (ou nœuds) et de relations entre les sommets (pas forcément tous) qui sont représentés par des arêtes.

Le graphe est pondéré si les arêtes sont affectées d’un nombre que l’on appelle poids de l’arête.

Exemple
On peut représenter le réseau routier entre Rennes et Grenoble par un graphe dont les sommets représentent les différentes villes et les arêtes les distances en km, comme le montre la figure suivante.

Toutes les arêtes sont affectées d’une distance, elles sont donc pondérées : le graphe est donc ici pondéré par des distances.

Exemple de graphe routier
Le calcul d’un itinéraire

La recherche d’un itinéraire dans un réseau routier est modélisée par la recherche d’une chaine dans le graphe pondéré qui représente ce réseau.

Les 3 principales recherches sont les suivantes.

  • La recherche du plus court chemin peut être résolue à l’aide d’un graphe pondéré par des distances.
  • La recherche du trajet le plus rapide se fera à partir d’un graphe pondéré par des temps de parcours.
  • La recherche du trajet le moins cher se fera à partir d’un graphe pondéré par des couts de transport.

Il existe une multitude d’algorithmes qui permettent de calculer des itinéraires. Certains d’entre eux sont extrêmement puissants et tiennent compte du trafic en temps réel, en combinant le système de géolocalisation, les dispositifs de télécommunication et de cartographie numérique.

b. Algorithme de Dijkstra
Présentation

Toutes les applications actuelles de calcul d’itinéraires utilisent des technologies qui sont l’héritage des algorithmes de la théorie des graphes, comme l’algorithme de Dijkstra.

L’algorithme de Dijkstra a été formulé en 1959 et porte le nom de son inventeur qui est le mathématicien néerlandais Edsger Dijkstra. Il permet de résoudre le problème du plus court chemin entre 2 points sur un graphe pondéré.
Principe

Pour bien comprendre comment il fonctionne, on prend le graphe pondéré suivant, en considérant la recherche du plus court chemin pour aller de D (Départ) à A (Arrivée). Les sommets représentent des villes et les arêtes représentent des distances en kilomètre.


Exemple de graphe pondéré par les distances
Étape 0 – Établir le tableau

On représente l’algorithme de Dijkstra sous la forme d’un tableau qui possède autant de colonnes et de lignes qu’il y a de sommets.

On note le nom des sommets en tête des colonnes et on numérote les lignes de 1 au nombre de sommet (dans notre cas 6).

Cela correspond en réalité au nombre maximal d’étapes nécessaires comme le montre le tableau ci-dessous.

Étape 1 – Identifier et verrouiller le sommet de départ

On spécifie le sommet de départ et on marque 0. On le verrouille (en rouge) pour spécifier que l’on n’y reviendra pas.

Depuis ce sommet, on peut aller en B (on parcourt 3 km) ou en E (on parcourt 1 km).

La notation 3D signifie que l’on a parcouru 3 km depuis le départ, et que l’on vient du sommet D.

Étape 2 – Identifier et verrouiller le sommet qui a le bilan le plus court parmi les sommets non verrouillés

On cherche maintenant le sommet qui a le bilan le plus court parmi les sommets non verrouillés (3 ou 1) : c’est E (en provenance de D), donc on le verrouille (en rouge).

Depuis E, on peut aller en B (on parcourt 1 km de plus), en C (on parcourt 3 km de plus), ou en F (on parcourt 5 km de plus).

Étape 3 – Identifier et verrouiller le sommet qui a le bilan le plus court parmi les sommets non verrouillés

On continue la recherche du sommet qui a le bilan le plus court parmi les sommets non verrouillés (2, 4 ou 6). Il faut tenir compte de toutes les cases de la colonnes. C’est B (en provenance de E), donc on le verrouille. (ça aurait pu être B en provenance de D si le bilan avait été plus court !).

Depuis B, on peut uniquement aller en C (on parcourt 2 km de plus).

Étape 4 – Identifier et verrouiller le sommet qui a le bilan le plus court parmi les sommets non verrouillés

On continue la recherche du sommet qui a le bilan le plus court parmi les sommets non verrouillés : c’est C (en provenance de E ou de B), donc on le verrouille.

Depuis C, on peut aller en F (on parcourt 1 km de plus) ou en A (on parcourt 3 km de plus).

Étape 5 – Identifier et verrouiller le sommet qui a le bilan le plus court parmi les sommets non verrouillés

On continue la recherche du sommet qui a le bilan le plus court parmi les sommets non verrouillés (5 ou 7) : c’est F (en provenance de C), donc on le verrouille.

Depuis F, on peut uniquement aller en A (on parcourt 1 km de plus).

Étape 6 – Identifier et verrouiller le sommet qui a le bilan le plus court parmi les sommets non verrouillés

On continue la recherche du sommet qui a le bilan le plus court parmi les sommets non verrouillés : c’est A (en provenance de F).

C’est terminé, puisque tous les sommets ont été verrouillés.

Étape 7 – Lire le tableau

Il ne nous reste plus qu’à lire le tableau pour avoir le plus court chemin. On souhaitait se rendre en A. On regarde la colonne du sommet A, on voit qu’au minimum on a parcouru 6 km en provenance de F.

On se place maintenant dans la colonne F, on voit que l’on vient de C, qui lui-même provient de E (on a choisi ce cas), qui lui-même provient de D.

Le chemin est donc le suivant :

D – E – C – F – A
ou D – E – B – C – F – A si on a retenu 4B à l’étape 4

On peut dire que cet algorithme permet d’avoir pour chaque sommet (la colonne du tableau) un sommet de provenance (la lettre qui se trouve en indice rouge) qui correspond au chemin le plus court et une distance cumulée depuis le sommet de départ.

Comment as-tu trouvé ce cours ?

Évalue ce cours !

 

Question 1/5

La médiane de 6 notes est 13. Cela signifie que :

Question 2/5

On a obtenu la série statistique suivante :

Combien vaut la médiane ?

Question 3/5

On a obtenu la série ci-dessous :

Quelle est la médiane de cette série ?

Question 4/5

On a relevé les tailles en cm des élèves d’une classe :

 

Parmi les propositions suivantes, laquelle est vraie ?

Question 5/5

Les notes en français de deux classes littéraires sont données dans le tableau suivant :

Quelle est la note médiane ?

Vous avez obtenu75%de bonnes réponses !

Reçois l’intégralité des bonnes réponses ainsi que les rappels de cours associés

Une erreur s'est produite, veuillez ré-essayer

Consultez votre boite email, vous y trouverez vos résultats de quiz!

Découvrez le soutien scolaire en ligne avec myMaxicours

Le service propose une plateforme de contenus interactifs, ludiques et variés pour les élèves du CP à la Terminale. Nous proposons des univers adaptés aux tranches d'âge afin de favoriser la concentration, encourager et motiver quel que soit le niveau. Nous souhaitons que chacun se sente bien pour apprendre et progresser en toute sérénité ! 

Fiches de cours les plus recherchées

SNT

La confidentialité de la localisation

SNT

Capteurs et actionneurs

SNT

Les interfaces homme-machine

SNT

La conception d'une IHM

SNT

Les paramètres d'une image numérique

SNT

Les métadonnées d'une image numérique

SNT

Le traitement d'une image numérique

SNT

Le rôle des algorithmes dans les appareils photo numériques

SNT

Le capteur, les photosites et le passage aux pixels

SNT

Les protocoles de transfert du web