APSP on Sparse Directed Unweighted Graphs: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "{{DISPLAYTITLE:APSP on Sparse Directed Unweighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is directed, and is unweighted (or equivalently, has all unit 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 Gr...")
 
No edit summary
 
(One intermediate revision by the same user not shown)
Line 12: Line 12:
== Parameters ==  
== Parameters ==  


<pre>n: number of vertices
$n$: number of vertices
m: number of edges</pre>
 
$m$: number of edges


== Table of Algorithms ==  
== Table of Algorithms ==  


Currently no algorithms in our database for the given problem.
Currently no algorithms in our database for the given problem.

Latest revision as of 08:52, 10 April 2023