Shortest path applications

The shortest paths between places and sets of places have a long history in graph theory. Originally, this problem arose from a question about traversing the seven bridges of Königsberg, Germany. In 1736, Leonhard Euler posited that a route that crossed each bridge to a region next to one side of a bridge exactly once did not exist. Indeed, this is the case. If there is one more region than the number of bridges for an odd number of bridges, a trip is possible without traversing bridges more than once. Note that the proof of this is beyond the scope of this book; if you are interested, you can find many proofs online if you search for proofs of the Königsberg bridge problem.

However, problems such as this come up often in the transportation industry and global positioning system (GPS) routing solutions and algorithms that calculate shortest paths with or without specific constraints such as the Königsberg bridge problem are common in routing...