APSP: Difference between revisions
No edit summary |
No edit summary |
||
| 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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/citation.cfm?id=368168 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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/science/article/pii/S0022000085710781?via%3Dihub 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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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] | |||
|- | |||
| [[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 (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] | |||
|- | |- | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:All-Pairs Shortest Paths (APSP) - APSP - Time.png|1000px]] | [[File:All-Pairs Shortest Paths (APSP) - APSP - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:All-Pairs Shortest Paths (APSP) - APSP - Space.png|1000px]] | [[File:All-Pairs Shortest Paths (APSP) - APSP - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[File:All-Pairs Shortest Paths (APSP) - APSP - Pareto Frontier.png|1000px]] | [[File:All-Pairs Shortest Paths (APSP) - APSP - Pareto Frontier.png|1000px]] | ||
Revision as of 13:04, 15 February 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(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 |