APSP: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(2 intermediate revisions by the same user not shown)
Line 12: Line 12:
== Parameters ==  
== Parameters ==  


n: number of vertices
$n$: number of vertices


m: number of edges
$m$: number of edges


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 24: Line 24:
|-
|-


| [[Shimbel Algorithm (APSP on Dense Directed Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP))|Shimbel Algorithm]] || 1953 || $O(V^{4})$ || $O(V^{2})$ || Exact || Deterministic || [https://link.springer.com/article/10.1007/BF02476438 Time]
| [[Shimbel Algorithm (APSP on Dense Directed Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP))|Shimbel Algorithm]] || 1953 || $O(n^{4})$ || $O(n^{2})$ || Exact || Deterministic || [https://link.springer.com/article/10.1007/BF02476438 Time]
|-
|-
| [[Floyd–Warshall algorithm (APSP All-Pairs Shortest Paths (APSP))|Floyd–Warshall algorithm]] || 1962 || $O(V^{3})$ || $O(V^{2})$ || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=368168 Time]
| [[Floyd–Warshall algorithm (APSP All-Pairs Shortest Paths (APSP))|Floyd–Warshall algorithm]] || 1962 || $O(n^{3})$ || $O(n^{2})$ || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=368168 Time]
|-
|-
| [[Seidel's algorithm (APSP on Dense Undirected Unweighted Graphs; APSP on Sparse Undirected Unweighted Graphs All-Pairs Shortest Paths (APSP))|Seidel's algorithm]] || 1995 || $O (V^{2.{37}3} \log V)$ || $O(V^{2})$ || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/S0022000085710781?via%3Dihub Time]
| [[Seidel's algorithm (APSP on Dense Undirected Unweighted Graphs; APSP on Sparse Undirected Unweighted Graphs All-Pairs Shortest Paths (APSP))|Seidel's algorithm]] || 1995 || $O (n^{2.{37}3} \log n)$ || $O(n^{2})$ || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/S0022000085710781 Time]
|-
|-
| [[Williams (APSP on Dense Directed Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP))|Williams]] || 2014 || $O(V^{3} /{2}^{(\log V)^{0.5}})$ || $O(V^{2})$ || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=2591811 Time]
| [[Williams (APSP on Dense Directed Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP))|Williams]] || 2014 || $O(n^{3} /{2}^{(\log n)^{0.5}})$ || $O(n^{2})$ || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=2591811 Time]
|-
|-
| [[Pettie & Ramachandran (APSP on Dense Undirected Graphs with Arbitrary Weights; APSP on Sparse Undirected Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP))|Pettie & Ramachandran]] || 2002 || $O(EV \log \alpha(E,V))$ ||  || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=545417 Time]
| [[Pettie & Ramachandran (APSP on Dense Undirected Graphs with Arbitrary Weights; APSP on Sparse Undirected Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP))|Pettie & Ramachandran]] || 2002 || $O(mn \log \alpha(m,n))$ ||  || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=545417 Time]
|-
|-
| [[Thorup (APSP on Dense Undirected Graphs with Positive Integer Weights; APSP on Sparse Undirected Graphs with Positive Integer Weights All-Pairs Shortest Paths (APSP))|Thorup]] || 1999 || $O(EV)$ || $O(EV)$ || Exact || Deterministic || [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7128&rep=rep1&type=pdf Time] & [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7128&rep=rep1&type=pdf Space]
| [[Thorup (APSP on Dense Undirected Graphs with Positive Integer Weights; APSP on Sparse Undirected Graphs with Positive Integer Weights All-Pairs Shortest Paths (APSP))|Thorup]] || 1999 || $O(mn)$ || $O(mn)$ || Exact || Deterministic || [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7128&rep=rep1&type=pdf Time] & [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7128&rep=rep1&type=pdf Space]
|-
|-
| [[Chan (Geometrically Weighted) (APSP on Geometrically Weighted Graphs All-Pairs Shortest Paths (APSP))|Chan (Geometrically Weighted)]] || 2009 || $O(V^{2.{84}4})$ || $O(l V^{2})$ || Exact || Deterministic || [http://tmc.web.engr.illinois.edu/moreapsp.pdf Time]
| [[Chan (Geometrically Weighted) (APSP on Geometrically Weighted Graphs All-Pairs Shortest Paths (APSP))|Chan (Geometrically Weighted)]] || 2009 || $O(n^{2.{84}4})$ || $O(l n^{2})$ || Exact || Deterministic || [http://tmc.web.engr.illinois.edu/moreapsp.pdf Time]
|-
|-
| [[Chan (APSP on Dense Directed Graphs with Arbitrary Weights; APSP on Dense Undirected Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP))|Chan]] || 2009 || $O(V^{3} \log^{3} \log V / \log^{2} V)$ || $O(V^{2})$ || Exact || Deterministic || [http://tmc.web.engr.illinois.edu/moreapsp.pdf Time]
| [[Chan (APSP on Dense Directed Graphs with Arbitrary Weights; APSP on Dense Undirected Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP))|Chan]] || 2009 || $O(n^{3} \log^{3} \log n / \log^{2} n)$ || $O(n^{2})$ || Exact || Deterministic || [http://tmc.web.engr.illinois.edu/moreapsp.pdf Time]
|-
|-
|}
|}
Line 45: Line 45:


[[File:All-Pairs Shortest Paths (APSP) - APSP - Time.png|1000px]]
[[File:All-Pairs Shortest Paths (APSP) - APSP - Time.png|1000px]]
== Space Complexity Graph ==
[[File:All-Pairs Shortest Paths (APSP) - APSP - Space.png|1000px]]
== Space-Time Tradeoff Improvements ==
[[File:All-Pairs Shortest Paths (APSP) - APSP - Pareto Frontier.png|1000px]]

Latest revision as of 09:06, 28 April 2023

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(n^{4})$ $O(n^{2})$ Exact Deterministic Time
Floyd–Warshall algorithm 1962 $O(n^{3})$ $O(n^{2})$ Exact Deterministic Time
Seidel's algorithm 1995 $O (n^{2.{37}3} \log n)$ $O(n^{2})$ Exact Deterministic Time
Williams 2014 $O(n^{3} /{2}^{(\log n)^{0.5}})$ $O(n^{2})$ Exact Deterministic Time
Pettie & Ramachandran 2002 $O(mn \log \alpha(m,n))$ Exact Deterministic Time
Thorup 1999 $O(mn)$ $O(mn)$ Exact Deterministic Time & Space
Chan (Geometrically Weighted) 2009 $O(n^{2.{84}4})$ $O(l n^{2})$ Exact Deterministic Time
Chan 2009 $O(n^{3} \log^{3} \log n / \log^{2} n)$ $O(n^{2})$ Exact Deterministic Time

Time Complexity Graph

All-Pairs Shortest Paths (APSP) - APSP - Time.png

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=APSP&oldid=47660"