Prerequisite: Graph Concepts, Graph Search
Shortest Path is defined as the path through a graph for which the sum of the edge weights is the smallest. In unweighted graphs, this is sometimes referred to as degrees of separation. Calculating the shortest path is a commonly encountered challenge for professional programmers. Luckily, there are many existing well defined algorithms that fit almost any situation.
Applications
- Shortest distance between two places on a map (driving directions).
- Determining degrees of separation such as finding a Erdos number, or the more recent Bacon number.
- Internet routing
Source Code
Relevant Directories:
Click here for build and run instructions