Shortest path

The shortest paths problem is one of the most fundamental problems in graph theory. Given a directed graph $G = (V,E)$, possibly weighted, and a set of pairs of vertices $\{(u_1,v_1), ..., (u_n,v_n)\}, u_i, v_i \in V$, the problem is to compute, for each $i$, a path in $G$ from $u_i$ to $v_i$ (a list of vertices $u_i = s_{i,0}, s_{i,1}, ..., s_{i,k} = v_i$ such that for all $0 \leq j < k$, $(s_{i,j},s_{i,j+1}) \in E$) such that no other path in $G$ from $u_i$ to $v_i$ 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.

Variations

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 $(u,v)$ 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 $\{u\} \times V$. One vertex, $u$, 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 $V \times V$; that is, we wish to know the shortest paths from every vertex to every other vertex.