When trying to find applications for shortest pathfinders on a graph, we think of car navigation via GPS, but there are many more use cases. This section gives an overview of the different applications of pathfinding. We will talk about networks and video games, and give an introduction to the traveling-salesman problem.
Routing within a network
Routing often refers to GPS navigation, but some more surprising applications are also possible.
GPS
The name GPS is actually used for two different technologies:
- The Global Positioning System (GPS) itself is a way of finding your precise location on Earth. It is made possible by a constellation of satellites orbiting around the planet and sending continuous signals. Depending on which signals your device receives, an algorithm based on triangulation methods can determine your position.
The satellites used by the GPS system all belong to the USA. Equivalent systems...