Chapitre VIII - Une voiture nous attend - L’Agrapheur – Intrigues policières à saveur mathématique

Polytechnique > L’Agrapheur > Chapitre VIII - Une voiture nous attend

Chapitre VIII - Une voiture nous attend

Dans le chapitre VIII, Manori résout deux problèmes en déterminant le plus court ou le plus long chemin qui permet de se rendre d’un sommet à un autre dans un graphe. Le problème de l’évasion des quatre prisonniers n’est en fait qu’une variante d’une célèbre énigme qu’on peut trouver un peu partout sur Internet et dont l’origine est inconnue. Il s’agit de transporter quatre personnes d’une rive à l’autre d’une rivière à l’aide d’un bateau sur lequel ne peuvent embarquer qu’au plus deux personnes à la fois. Certains préfèrent remplacer le bateau par un pont délabré qui ne peut pas supporter le poids de plus de deux personnes. La nuit noire rend l’usage d’une torche nécessaire, mais oblige le retour d’une personne après chaque traversée à deux. Dans mon histoire des prisonniers, le pont a été remplacé par un tunnel.

De nombreuses techniques ont été proposées pour déterminer de manière efficace, dans un graphe, les plus courts ou les plus longs chemins. Les méthodes les plus connues sont certainement les algorithmes de Dijkstra, de Bellman et de Floyd qu’on retrouve dans presque tous les livres d’introduction à la théorie des graphes, y compris dans [West01].

Notes pédagogiques - Plus courts et plus longs chemins