GPS : comment Dijkstra trouve-t-il le plus court chemin ?

Intervenant 10:00

Bonjour et bienvenue à tout le monde dans le podcast du magazine Tangente. Bonjour. On a tous déjà entendu cette petite voix familière qui nous dit au prochain rond-point, prenez la deuxième sortie. Ah oui,

Intervenant 20:11

le fameux GPS de tous les

Intervenant 10:13

jours. Voilà. Et face à un labyrinthe de goudron vraiment immense, la machine trouve le chemin parfait en une fraction de seconde. Et la petite exploration d'aujourd'hui basée sur nos dossiers, c'est justement de décortiquer les mathématiques qui se cachent derrière ce miracle urbain.

Intervenant 20:28

Pour démystifier tout ça, il faut en fait remplacer l'asphalte par de la géométrie pure. Le réseau routier, on le modélise par ce qu'on appelle un graphe.

Intervenant 10:37

Un graphe, d'accord.

Intervenant 20:37

C'est ça. Donc les intersections deviennent des sommets, et les routes qui relient ces sommets, on appelle ça des arêtes.

Intervenant 10:44

Des arêtes.

Intervenant 20:45

Ouais. Et chaque arête a un poids bien précis. Un poids.

Intervenant 10:49

C'est-à-dire genre la distance ou le temps de trajet ?

Intervenant 20:53

Exactement, des kilomètres ou des minutes.

Intervenant 10:56

Sauf que à l'échelle d'un pays entier, on parle de millions d'intersections.

Intervenant 21:00

Oui, les combinaisons sont littéralement infinies.

Intervenant 11:03

Du coup, comment l'ordinateur fait pour ne pas surchauffer ou calculer pendant des heures avant de nous donner la route ?

Intervenant 21:09

Alors, la réponse, elle nous vient de 1959, grâce à un informaticien néerlandais, Edger Dystra. Son algorithme se base sur le principe d'optimalité d'un certain Richard Bellman.

Intervenant 11:20

Ok, et ça dit quoi ce principe ?