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
Videos
Application mobile

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.