All Pairs Shortest Path (APSP)

1 Formulation of the problem

Let [math]G = (V, E)[/math] be a given graph with edge weights [math]f(e)[/math], [math]e \in E[/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]. We say that [math]v[/math] is reachable from [math]u[/math] if there exists at least one path [math]P(u, v)[/math]. The total weight of this path is

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

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

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

2 Variants of the problem

If a shortest path is required only for a single source rather than for all vertices, then see single source 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 quadratic time by using the breadth first search.
• Integer weights . The problem can again be solved in quadratic 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.

Depending on the organization of calculations, the following variants are possible:

• static graph: Calculation of all shortest paths (classical approach);
• online calculation : Certain preliminary calculations are performed; then a path between two vertices is found by inquiry. (This approach is reasonable if the shortest paths are actually needed only for certain vertex pairs, but these pairs are not a priori known);
• dynamic graph : edges and vertices may be added or removed, which is accompanied by the recalculation of the shortest paths. (This variant is appropriate for permanently varying graphs, for instance, social networks.)

3 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]).

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

Output data (possible variants):

1. for each vertex pair [math](u, v)[/math] of the original graph: the last edge [math]e^*_v = (w, v)[/math] of the shortest path leading from the vertex [math]u[/math] to [math]v[/math] or the corresponding vertex [math]w[/math];
2. for each vertex pair [math](u, v)[/math] of the original graph: the total weight [math]f^*(u, 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^2)[/math].

3.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^*_{uw}[/math] are passed in the reverse direction until the vertex [math]u[/math] is visited.

The edges [math]e^*_{uv}[/math] can be regenerated in time [math]O(mn)[/math] by sorting the edges for each vertex according to the rule

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

The sorting can be performed in parallel.

For the given vertex [math]u[/math], the search for shortest distances [math]f^*(u, v)[/math] for the set of edges [math]e^*_{uv}[/math] should be preceded by the construction of a tree from these edges. Then the breadth first search with time complexity [math]O(m)[/math] (and with the possibility of parallelization) is applied to this tree. The total time for all vertex pairs is [math]O(mn)[/math].

4 Algorithms for solving the problem

• Johnson's algorithm for directed graphs with arbitrary weights. The complexity is [math]O(mn+ n^2 \ln n)[/math].
• The Floyd--Warshall algorithm for directed graphs with arbitrary weights. The complexity is [math]O(n^3)[/math].
• Repeated application of any algorithm for the single source shortest path:
  • Breadth first search (BFS) for directed unweighted graphs. The complexity is [math]O(mn)[/math].
  • Dijkstra's algorithm for directed graphs with nonnegative weights. The complexity is [math]O(mn + n^2 \ln n)[/math].
  • The Bellman--Ford algorithm for directed graphs with arbitrary weights. The complexity is [math]O(mn^2)[/math].
  • Δ-stepping algorithm for directed graphs with nonnegative weights. The average-case complexity for graphs with random weights is [math]O(n(n + m + dL))[/math]; the parallel complexity is [math]O((dL + \ln n) n \ln n[/math], and the average-case work is [math]O(n (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(mn)[/math].
  • For a directed acyclic graph with arbitrary weights, the algorithm is based on the topological sorting of the graph. The complexity is [math]O(mn)[/math].

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.

5 Parallelization resource

The problem can be solved by applying any algorithm for the single source shortest path to all the vertices of the graph. For different vertices, the calculations are independent and may be performed in parallel.

Since the size of the output data is quadratic and the complexity of calculations is higher than quadratic, it makes sense to perform a preliminary processing of the data and use various graph decompositions in order to reduce the original problem to the parallel finding of shortest paths on smaller subgraphs :

• selection of connected components;
• selection of subgraphs connected only by bridges (that is, by edges whose removal makes the graph disconnected);
• selection of biconnected components connected only by joints (also called articulation points or cut vertices; these are vertices вершины, whose removal makes the graph disconnected);
• removal of hanging vertices (that is, vertices having at most one adjacent vertex).

Which decompositions are advantageous in a specific situation depends on the structure of the graph and can be determined only by analyzing this structure.