Route-finding

Sometimes, very different-sounding problems turn out to be similar when you think about how to solve them. What do Pac-Man, the royal family of Britain, and driving to Orlando have in common? They all involve route-finding or path-search problems:

• How is the current Prince William related to King William III, who endowed the College of William and Mary in 1693?
  

• What path should a ghost follow to get to Pac-Man as quickly as possible?
  

• What's the best way to drive from Dallas, Texas to Orlando, Florida?
  

We have to be given some information to answer any of these questions.

For example, a family tree of the royal family of Britain would show connections between people who were directly related. Prince William is the son of Charles Philip Arthur Windsor. Charles is the son of Queen Elizabeth II. The problem is to find a short chain on the family tree connecting Prince William and William III, using these direct connections. As you can see from the tree below, it might take quite a few connections.