Single Source Shortest Path (SSSP)

1 Formulation of the problem

Let [math]G = (V, E)[/math] be a given graph with edge weights [math]f(e)[/math] and a marked vertex (called the source) [math]u[/math]. The sequence [math]P(u, v)[/math] of edges [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] is called a "path from the vertex [math]u[/math] to [math]v[/math]. The total weight of this path is defined as

[math] f(P(u, v)) = \sum_{i = 1}^k f(e_i). [/math]

For each vertex [math]v[/math] that is reachable from the source [math]u[/math], it is required to indicate a path [math]P^*(u, v)[/math] having the minimum possible total weight:

[math] f^*(v) = f(P^*(u, v)) = \min f(P(u, v)). [/math]

2 Variants of the problem

If shortest paths are needed for all the vertices rather than for a single one, then see all pairs shortest path.

This problem can be stated for both directed and undirected graphs. The above formulation is applicable in both cases.

Depending on possible values of the weights, the following cases may be distinguished:

• Unit weights. In this case, the problem significantly simplifies and can be solved in linear time by using the breadth first search.
• Integer weights . The problem can again be solved in linear time (though with a larger constant in the complexity estimate).
• Nonnegative weights. A constraint commonly occurring in practice is that the edge weights correspond to the times (or costs) of passing through portions of the route and, hence, cannot be negative.
• Arbitrary weights. This is the most general situation. The graph should not contain cycles with a negative total weight; otherwise, there is no shortest path.

3 Properties of the problem

The solution to the problem satisfies the following optimality principle: If the path [math]P^*(u, w)[/math] is a part of the shortest path [math]P^*(u, v)[/math], then [math]P^*(u, w)[/math] is the shortest path from the source [math]u[/math] to the vertex [math]w[/math].

The optimality principle implies that, for each vertex [math]v[/math], it suffices to store only the last edge [math]e^*_v[/math] of the shortest path [math]P^*(u, v)[/math] rather than the entire path. Consequently, the storage estimate is [math]O(m)[/math], where [math]m[/math] is the number of edges.

4 Input and output data

Input data: weighted graph [math](V, E, W)[/math] ([math]n[/math] vertices [math]v_i[/math] and [math]m[/math] edges [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] with weights [math]f_j[/math]), source [math]u[/math].

Size of the input data: [math]O(m + n)[/math].

Output data (possible variants):

1. for each vertex [math]v[/math] of the original graph: the last edge [math]e^*_v = (w, v)[/math] of the shortest path leading from the source [math]u[/math] to [math]v[/math] or the corresponding vertex [math]w[/math];
2. for each vertex [math]v[/math] of the original graph: the total weight [math]f^*(v)[/math] of the shortest path leading from the source [math]u[/math] to [math]v[/math].

Size of the output data: [math]O(n)[/math].

4.1 Output data conversion and shortest path search

The shortest path from [math]u[/math] to [math]v[/math] can be reconstructed in time [math]O(\left |P^*(u, v) \right |)[/math] if, starting from the vertex [math]v[/math], the edges [math]e^*_w[/math] are passed in the reverse direction until the source [math]u[/math] is visited.

The edges [math]e^*_v[/math] can be regenerated in time [math]O(m)[/math] by sorting the edges according to the rule

[math] e^*_v \in \{ (w, v) \in E \mid f^*(v) = f^*(w) + f((v, w)) \}. [/math]

The sorting can be performed in parallel.

The search for shortest distances [math]f^*(v)[/math] for the given set of edges [math]e^*_v[/math] should be preceded by the construction of a tree. Then the breadth first search is applied to this tree. The time complexity is [math]O(m)[/math] (with the possibility of parallelization).

5 Algorithms for solving the problem

• Breadth first search (BFS) for directed unweighted graphs. The complexity is [math]O(m)[/math].
• Dijkstra's algorithm for directed graphs with nonnegative weights. The complexity is [math]O(m + n \ln n)[/math].
• The Bellman--Ford algorithm for directed graphs with arbitrary weights. The complexity is [math]O(mn)[/math].
• Δ-stepping algorithm for directed graphs with nonnegative weights. The average-case complexity for graphs with random weights is [math]O(n + m + dL)[/math]; the parallel complexity is [math]O((dL + \ln n) \ln n[/math], and the average-case work is [math]O(n + m + dL \ln n)[/math].
• The Thorup algorithm is a theoretical proof of the fact that the problem for undirected graphs with positive integer weights can be solved in linear time [math]O(m)[/math].
• For a directed acyclic graph with arbitrary weights, the search for a shortest path has linear time complexity [math]O(m + n)[/math]. The algorithm is based on the topological sorting of the graph.

Notation: [math]m[/math] is the number of edges, [math]n[/math] is the number of vertices, [math]d[/math] is the maximum degree of a vertex, and [math]L[/math] is the maximum total weight of a shortest path.

The algorithms listed above can also be used for solving the APSP problem All Pairs Shortest Path. (To this end, the corresponding algorithm should be run for each vertex of the graph, which, if required, can be done in parallel.) In this case, the complexity estimate is multiplied by [math]n[/math].