Graph Shortest Path Algorithms

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.

Source Code

Full Repo

Relevant Directories:

Click here for build and run instructions