View source for APSP on Dense Undirected Graphs with Arbitrary Weights

{{DISPLAYTITLE:APSP on Dense Undirected 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 undirected, and has arbitrary weights.

== Related Problems == 

Generalizations: [[APSP]]

Related: [[APSP on Dense Directed 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 == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[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(mn \log \alpha(m,n))$ ||  || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/citation.cfm?id=545417 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 Graph == 

[[File:All-Pairs Shortest Paths (APSP) - APSP on Dense Undirected Graphs with Arbitrary Weights - Time.png|1000px]]