Calculer un itinéraire

Tu demandes un trajet à ton téléphone, il te répond en une fraction de seconde, alors qu'il existe des millions de chemins possibles. Comment fait-il ?

La réponse va te surprendre : tu sais déjà. Un calcul d'itinéraire est un problème de graphe, et tu as passé un chapitre entier dessus.

Cours ici, exercices sur Capytale

Cette page est le cours. Les exercices sont sur Capytale.

Une carte routière est un graphe

Regarde une carte, et oublie le dessin. Ne garde que l'essentiel :

les intersections (carrefours, villes, points d'intérêt) deviennent des sommets ;
les routes qui les relient deviennent des arêtes.

C'est tout. Une carte routière est un graphe, et tu sais lire un graphe depuis le chapitre sur les réseaux sociaux.

Mais toutes les routes ne se valent pas

Voilà la nouveauté, et c'est la seule de la séance.

Dans le graphe des amitiés, toutes les arêtes étaient équivalentes : on était ami, ou on ne l'était pas. Ici, non : une route peut faire 2 km ou 50 km. Les arêtes ne se valent plus.

On leur donne donc un poids : un nombre porté par chaque arête, qui dit ce qu'elle coûte. On parle de graphe pondéré.

Les nombres en rouge sont les distances en kilomètres.

Le plus court chemin n'est pas le plus direct

Exercice - Aller du Lycée à la Gare

Une route directe relie le Lycée à la Gare : elle fait 8 km.

Cherche maintenant s'il existe un chemin plus court, quitte à passer par d'autres endroits. Donne le meilleur trajet et sa longueur.

Correction

Le meilleur trajet est Lycée, Mairie, Parc, Gare : \(2 + 2 + 3 = \mathbf{7}\) km.

C'est plus court que la route directe (8 km), alors qu'il emprunte trois routes au lieu d'une.

(Vérifie les autres possibilités : Lycée, Mairie, Stade, Gare fait \(2+5+4 = 11\) km ; Lycée, Mairie, Parc, Piscine, Gare fait \(2+2+6+2 = 12\) km. Le meilleur est bien 7.)

La leçon

Le plus court chemin n'est pas celui qui passe par le moins de routes. Il faut compter les kilomètres, pas les arêtes.

C'est exactement ce que fait ton GPS quand il te propose un détour qui « a l'air » plus long sur la carte, mais qui est réellement plus rapide. Ton œil compte les traits ; l'algorithme compte les poids.

Court, ou rapide ?

Le poids d'une arête n'est pas obligatoirement une distance. On peut y mettre ce qu'on veut, et c'est ce qui rend l'outil si puissant :

Si le poids est…	l'algorithme trouve…
la distance en km	le trajet le plus court
la durée en minutes	le trajet le plus rapide
la consommation de carburant	le trajet le plus économique
le dénivelé	le trajet le moins fatigant (à vélo)

Le même algorithme, sur le même graphe. Seuls les poids changent.

C'est pourquoi ton application te propose « le plus rapide », « le plus court » ou « éviter les péages » : elle ne change pas de méthode, elle change de poids.

Et les embouteillages ?

Un trajet rapide à 3 h du matin ne l'est plus à 8 h. Les applications mettent donc à jour les poids en temps réel, à partir de la position des téléphones qui roulent.

Autrement dit : c'est toi qui alimentes le calcul. Ton téléphone signale ta vitesse, ce qui permet de savoir que cette route est bouchée, ce qui permet d'en dévier les autres. Tu es à la fois utilisateur et capteur.

Faire calculer la machine

Sur six lieux, tu trouves le meilleur trajet à la main. Sur le réseau routier français (des millions d'intersections), c'est impossible.

Comme pour les graphes d'amitié, on déclare le graphe, une route à la fois, en précisant son poids :

import networkx as nx

ville = nx.Graph()

ville.add_edge("Lycée", "Gare", km=8)
ville.add_edge("Lycée", "Mairie", km=2)
ville.add_edge("Mairie", "Parc", km=2)
ville.add_edge("Parc", "Gare", km=3)

Le km=8 est le poids de la route. Puis on demande le meilleur trajet :

print(nx.shortest_path(ville, "Lycée", "Gare", weight="km"))
print(nx.shortest_path_length(ville, "Lycée", "Gare", weight="km"))

affiche :

['Lycée', 'Mairie', 'Parc', 'Gare']
7

Ce sont tes résultats. La machine a appliqué la même méthode que toi, en comparant tous les chemins possibles, mais elle peut le faire sur des millions de routes.

Le mot weight n'est pas décoratif

Si tu écris nx.shortest_path(ville, "Lycée", "Gare") en oubliant weight="km", la machine ignore les distances et cherche le chemin avec le moins d'arêtes. Elle te répondra ['Lycée', 'Gare'] : la route directe de 8 km.

Ce n'est pas un bug : c'est ce que tu lui as demandé. Une machine fait ce qu'on lui dit, pas ce qu'on veut.

Ce qu'on retient

Une carte routière est un graphe : les intersections sont les sommets, les routes les arêtes.
Un graphe pondéré porte un poids sur chaque arête (sa distance, sa durée, son coût).
Le plus court chemin minimise la somme des poids, pas le nombre d'arêtes : il passe souvent par plus de routes que le trajet direct.
Changer le sens du poids (km, minutes, carburant, dénivelé) change le résultat sans changer l'algorithme : « le plus court », « le plus rapide » et « le moins cher » sont le même calcul avec des poids différents.
Les embouteillages sont pris en compte en mettant à jour les poids en temps réel, à partir des téléphones qui roulent. Tu es aussi un capteur.
En Python : nx.shortest_path(graphe, depart, arrivee, weight="km"). Sans weight, la machine compte les arêtes, pas les kilomètres.

Et ensuite

Ton téléphone calcule ta position, et il alimente le trafic en temps réel. Il sait donc où tu es, et où tu as été. Dernière séance du thème : que devient cette information ?