Chapter VIII - The Getaway Car

In Chapter VIII, Manori solves two problems by determining the shortest or longest path to get from one vertex to another vertex in a graph. The puzzle of the four escaping prisoners is just a variant on a famous puzzle that you can find all over the internet; its origins are unknown. The puzzle is to move four people from one side of a river to the other using one boat that can only carry two people at a time. Some prefer to replace the boat by a broken-down bridge that can only hold the weight of two people. In my prisoner story, the bridge is replaced by a tunnel. Darkness makes it necessary to use a flashlight, but that means that one person has to return after each two-person trip.

Many techniques have been proposed for efficiently determining the shortest and longest paths in a graph. The best-known methods are certainly the algorithms of Dijkstra, Bellman and Floyd, which you can find in practically every introductory book on graph theory, including in West's book.

Teaching notes - Shortest and Longest Paths

 

• Home
• Chapter I
  Respecting the Rules
• Chapter II
  The Villas of the Bellevue
• Chapter III
  The Case of the Missing Files
• Chapter IV
  The Case of the Hidden Inheritance
• Chapter V
  An Unhappy Employee
• Chapter VI
  The Case of the Runaway Mouse
• Chapter VII
  The Case of the Hooded Man
• Chapter VIII
  The Getaway Car
• Chapter IX
  The Sudoku Apprentice
• Bibliography

Home :: Chapter I Respecting the Rules :: Chapter II The Villas of the Bellevue :: Chapter III The Case of the Missing Files :: Chapter IV The Case of the Hidden Inheritance :: Chapter V An Unhappy Employee :: Chapter VI The Case of the Runaway Mouse :: Chapter VII The Case of the Hooded Man :: Chapter VIII The Getaway Car :: Chapter IX The Sudoku Apprentice :: Bibliography