APSP on Dense Directed Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))
Revision as of 10:20, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Directed Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))}} == 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, A...")
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(V^{4})$ | $O(V^{2})$ | Exact | Deterministic | Time |
| Williams | 2014 | $O(V^{3} /{2}^{(\log V)^{0.5}})$ | $O(V^{2})$ | Exact | Deterministic | Time |
Time Complexity graph
_-_APSP_on_Dense_Directed_Graphs_with_Arbitrary_Weights_-_Time.png)
Space Complexity graph
_-_APSP_on_Dense_Directed_Graphs_with_Arbitrary_Weights_-_Space.png)
Pareto Decades graph
_-_APSP_on_Dense_Directed_Graphs_with_Arbitrary_Weights_-_Pareto_Frontier.png)