Problem level

All Pairs Shortest Path (APSP)

From Algowiki
Jump to: navigation, search

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 [1] (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 [2]: 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 [3]: 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[4] for directed graphs with arbitrary weights. The complexity is [math]O(mn+ n^2 \ln n)[/math].
  • The Floyd--Warshall algorithm[5][6][7] 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[8][9] for directed graphs with nonnegative weights. The complexity is [math]O(mn + n^2 \ln n)[/math].
    • The Bellman--Ford algorithm[10][11][12] for directed graphs with arbitrary weights. The complexity is [math]O(mn^2)[/math].
    • Δ-stepping algorithm[13] 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[1] 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 [14]:

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

6 References

  1. 1.0 1.1 Thorup, Mikkel. “Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time.” Journal of the ACM 46, no. 3 (May 1, 1999): 362–94. doi:10.1145/316542.316548.
  2. Djidjev, Hristo N, Grammati E Pantziou, and Christos D Zaroliagis. “On-Line and Dynamic Algorithms for Shortest Path Problems.” In Proceedings of STACS 95, 193–204. Lecture Notes in Computer Science Vol. 900, Berlin, Heidelberg: Springer, 1995. doi:10.1007/3-540-59042-0_73.
  3. Demetrescu, Camil, and Giuseppe F Italiano. “Fully Dynamic All Pairs Shortest Paths with Real Edge Weights.” Journal of Computer and System Sciences 72, no. 5 (August 2006): 813–37. doi:10.1016/j.jcss.2005.05.005.
  4. Johnson, Donald B. “Efficient Algorithms for Shortest Paths in Sparse Networks.” Journal of the ACM 24, no. 1 (January 1977): 1–13. doi:10.1145/321992.321993.
  5. Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.
  6. Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.
  7. Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.
  8. Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.
  9. Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1, 1987): 596–615. doi:10.1145/28869.28874.
  10. Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.
  11. Ford, L R. Network Flow Theory., RAND Corporation, 1958.
  12. Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.
  13. Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.
  14. Banerjee, Dip Sankar, Ashutosh Kumar, Meher Chaitanya, Shashank Sharma, and Kishore Kothapalli. “Work Efficient Parallel Algorithms for Large Graph Exploration on Emerging Heterogeneous Architectures.” Journal of Parallel and Distributed Computing, December 2014. doi:10.1016/j.jpdc.2014.11.006.