The shortest paths problem is one of the most fundamental problems in graph theory. Given a directed graph , possibly weighted, and a set of pairs of vertices , the problem is to compute, for each , a path in from to (a list of vertices such that for all , ) such that no other path in from to has a lower total weight.
Shortest paths in undirected graphs can be computed by replacing each undirected edge with two arcs of the same weight, one going in each direction, to obtain a directed graph.
Three variations of the shortest path algorithm exist, and they are discussed in the following sections.
- In the single-pair shortest path problem, there is only one pair in the problem set. In other words the shortest path is desired between a single pair of vertices.
- In the single-source shortest paths problem, the problem set is of the form . One vertex, , is designated the source, and we wish to find the shortest paths from the source to all other vertices. (To solve the analogous single-destination shortest paths problem, we merely reverse the directions of all edges, which reduces it to single-source.)
- In the all-pairs shortest paths problem, the problem set is ; that is, we wish to know the shortest paths from every vertex to every other vertex.