Carte routable et calcul d'un itinéraire

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

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

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.

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.

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

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.

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.

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

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

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

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

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.

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.