APSP (All-Pairs Shortest Paths (APSP))

Description

The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

Related Problems

Subproblem: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirected Graphs with Positive Integer Weights, APSP on Sparse Directed Graphs with Arbitrary Weights, APSP on Sparse Undirected Graphs with Positive Integer Weights, APSP on Sparse Undirected Graphs with Arbitrary Weights, APSP on Dense Directed Unweighted Graphs, APSP on Dense Undirected Unweighted Graphs, APSP on Sparse Directed Unweighted Graphs, APSP on Sparse Undirected Unweighted Graphs, (5/3)-approximate ap-shortest paths

Related: APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirected Graphs with Positive Integer Weights, APSP on Sparse Directed Graphs with Arbitrary Weights, APSP on Sparse Undirected Graphs with Positive Integer Weights, APSP on Sparse Undirected Graphs with Arbitrary Weights, APSP on Dense Directed Unweighted Graphs, APSP on Dense Undirected Unweighted Graphs, APSP on Sparse Directed Unweighted Graphs, APSP on Sparse Undirected Unweighted Graphs, (5/3)-approximate ap-shortest paths

Parameters

n: number of vertices

m: number of edges

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Shimbel Algorithm	1953	$O(V^{4})$	$O(V^{2})$	Exact	Deterministic	Time
Floyd–Warshall algorithm	1962	$O(V^{3})$	$O(V^{2})$	Exact	Deterministic	Time
Seidel's algorithm	1995	$O (V^{2.{37}3} \log V)$	$O(V^{2})$	Exact	Deterministic	Time
Williams	2014	$O(V^{3} /{2}^{(\log V)^{0.5}})$	$O(V^{2})$	Exact	Deterministic	Time
Pettie & Ramachandran	2002	$O(EV \log \alpha(E,V))$		Exact	Deterministic	Time
Thorup	1999	$O(EV)$	$O(EV)$	Exact	Deterministic	Time & Space
Chan (Geometrically Weighted)	2009	$O(V^{2.{84}4})$	$O(l V^{2})$	Exact	Deterministic	Time
Chan	2009	$O(V^{3} \log^{3} \log V / \log^{2} V)$	$O(V^{2})$	Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff