APSP on Dense Directed Graphs with Arbitrary Weights: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
(4 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( | | [[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] | ||
|- | |- | ||
| [[Williams (APSP on Dense Directed Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP))|Williams]] || 2014 || $O( | | [[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] | ||
|- | |||
| [[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] | |||
|- | |- | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:All-Pairs Shortest Paths (APSP) - APSP on Dense Directed Graphs with Arbitrary Weights - Time.png|1000px]] | [[File:All-Pairs Shortest Paths (APSP) - APSP on Dense Directed Graphs with Arbitrary Weights - Time.png|1000px]] | ||
Latest revision as of 10:06, 28 April 2023
Description
In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is directed, and has arbitrary weights.
Related Problems
Generalizations: APSP
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 |
Williams | 2014 | $O(n^{3} /{2}^{(\log n)^{0.5}})$ | $O(n^{2})$ | Exact | Deterministic | Time |
Chan | 2009 | $O(n^{3} \log^{3} \log n / \log^{2} n)$ | $O(n^{2})$ | Exact | Deterministic | Time |