APSP on Dense Directed Graphs with Arbitrary Weights: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
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]
|-
|-
| [[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]
|-
|-
| [[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]
|-
|-
|}
|}

Revision as of 08:52, 10 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

Time Complexity Graph

All-Pairs Shortest Paths (APSP) - APSP on Dense Directed Graphs with Arbitrary Weights - Time.png

Space Complexity Graph

All-Pairs Shortest Paths (APSP) - APSP on Dense Directed Graphs with Arbitrary Weights - Space.png

Time-Space Tradeoff

All-Pairs Shortest Paths (APSP) - APSP on Dense Directed Graphs with Arbitrary Weights - Pareto Frontier.png

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