View source for APSP on Sparse Undirected Graphs with Positive Integer Weights

{{DISPLAYTITLE:APSP on Sparse Undirected Graphs with Positive Integer Weights (All-Pairs Shortest Paths (APSP))}}
== Description == 

In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is undirected, and has positive integer weights.

== Related Problems == 

Generalizations: [[APSP]]

Related: [[APSP on Dense Directed Graphs with Arbitrary Weights]], [[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 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

|-

| [[Thorup (APSP on Dense Undirected Graphs with Positive Integer Weights; APSP on Sparse Undirected Graphs with Positive Integer Weights All-Pairs Shortest Paths (APSP))|Thorup]] || 1999 || $O(mn)$ || $O(mn)$ || Exact || Deterministic || [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7128&rep=rep1&type=pdf Time] & [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7128&rep=rep1&type=pdf Space]
|-
|}

== Time Complexity Graph == 

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