Shortest Path: Summary

  • Summarize shortest path algorithms.

Shortest Path Problem

Input: Graph $G=(V, E)$, and a starting vertex $s \in V$.
Goal: Identify the shortest path from $s$ to every vertex in $G$.

There are many variations of the Shortest Path problem:

  • weighted vs. unweighted (all weights equal)
  • cyclic vs. acyclic
  • positive weights only vs. negative weights allowed
  • single source vs. multi-source
  • etc.

The (modified) BFS can be used to solve the problem for the single-source unweighted graph. Dijkstra's algorithm can be used for a single-source weighted graph (when weights are non-negative). There are other algorithms for other variants of the problem. For instance, the Bellman–Ford algorithm, the Floyd–Warshall algorithm, the Johnson's algorithm, the Viterbi's algorithm, etc.