Variants

In this chapter, we shall focus on the single-source shortest-paths problem: given a graph G = (V, E), we want to find a shortest path from a given source vertex s ∈ V to each vertex v ∈ V . Many other problems can be solved by the algorithm for the single-source problem, including the following variants.

• Single-destination shortest-paths problem: Find a shortest path to a given destination vertex t from each vertex v. By reversing the direction of each edge in the graph, we can reduce this problem to a single-source problem.

• Single-pair shortest-path problem: Find a shortest path from u to v for given vertices u and v. If we solve the single-source problem with source vertex u, we solve this problem also. Moreover, no algorithms for this problem are known that run asymptotically faster than the best single-source algorithms in the worst case.

• All-pairs shortest-paths problem: Find a shortest path from u to v for every pair of vertices u and v. Although this problem can be solved by running a single-source algorithm once from each vertex, it can usually be solved faster. Additionally, its structure is of interest in its own right. Chapter 25 addresses the all-pairs problem in detail.