APSP on Dense Directed Graphs with Arbitrary Weights

In this case, the graph $G=(V,E)$ that we consider is dense ( $m = O(n^2)$ ), is directed, and has arbitrary weights.

Parameters

$n$ : number of vertices
$m$ : number of edges

Related Problems

APSP on Dense Undirected Graphs with Positive Integer Weights

APSP on Sparse Undirected Graphs with Positive Integer Weights

Approximate Distance Oracle

Directed, Weighted APSP

Undirected, Weighted APSP

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 3 of 3 algorithms

				See more
Williams	2014	$O(n^3/2^{\sqrt{\log n}})$	$O(n^2)$
Chan	2009	$O(n^3 \log^3 \log n / \log^2 n)$	$O(n^2)$
Shimbel Algorithm	1953	$O(n^4)$	$O(n^2)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table