All-Pairs Shortest Paths (APSP)

The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of the edges along the path is minimized. The goal of the all-pairs shortest path problem is to find such a shortest-path between all pairs of vertices in a given graph.

APSP

17 Algorithms


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.	4	Dense	Arbitrary Weight	Directed
APSP on Dense Undirected Graphs with Arbitrary Weights In this case, the graph $G=(V,E)$ that we consider is dense ( $m = O(n^2)$ ), is undirected, and has arbitrary weights.	2	Dense	Arbitrary Weight	Undirected
APSP on Dense Undirected Unweighted Graphs In this case, the graph $G=(V,E)$ that we consider is dense ( $m = O(n^2)$ ), is undirected, and is unweighted (or equivalently, has all unit weights).	1	Dense	Unweighted	Undirected
APSP on Geometrically Weighted Graphs In this case, the graph $G=(V,E)$ that we consider may be dense or sparse, may be directed or undirected, and has weights from a fixed set of $c$ values.	1	-	Geometric Weight	-
APSP on Sparse Undirected Graphs with Arbitrary Weights In this case, the graph $G=(V,E)$ that we consider is sparse ( $m = O(n)$ ), is undirected, and has arbitrary weights.	1	Sparse	Arbitrary Weight	Undirected
APSP on Sparse Undirected Unweighted Graphs In this case, the graph $G=(V,E)$ that we consider is sparse ( $m = O(n)$ ), is undirected, and is unweighted (or equivalently, has all unit weights).	1	Sparse	Unweighted	Undirected
APSP on Dense Directed Unweighted Graphs In this case, the graph $G=(V,E)$ that we consider is dense ( $m = O(n^2)$ ), is directed, and is unweighted (or equivalently, has all unit weights).	0	Dense	Unweighted	Directed
APSP on Sparse Directed Graphs with Arbitrary Weights In this case, the graph $G=(V,E)$ that we consider is sparse ( $m = O(n)$ ), is directed, and has arbitrary weights.	0	Sparse	Arbitrary Weight	Directed
APSP on Sparse Directed Unweighted Graphs 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).	0	Sparse	Unweighted	Directed

APSP
DDA
Dense, Directed, Arbitrary Weight
In this case, the graph $G=(V,E)$ that we consider is dense ( $m = O(n^2)$ ), is directed, and has arbitrary weights.
4 Algorithms
- APSP on Dense Directed Graphs with Arbitrary Weights
DUA
Dense, Undirected, Arbitrary Weight
In this case, the graph $G=(V,E)$ that we consider is dense ( $m = O(n^2)$ ), is undirected, and has arbitrary weights.
2 Algorithms
- APSP on Dense Undirected Graphs with Arbitrary Weights
DUU
Dense, Undirected, Unweighted
In this case, the graph $G=(V,E)$ that we consider is dense ( $m = O(n^2)$ ), is undirected, and is unweighted (or equivalently, has all unit weights).
1 Algorithms
- APSP on Dense Undirected Unweighted Graphs
GW
Geometric Weight
In this case, the graph $G=(V,E)$ that we consider may be dense or sparse, may be directed or undirected, and has weights from a fixed set of $c$ values.
1 Algorithms
- APSP on Geometrically Weighted Graphs
SUA
Sparse, Undirected, Arbitrary Weight
In this case, the graph $G=(V,E)$ that we consider is sparse ( $m = O(n)$ ), is undirected, and has arbitrary weights.
1 Algorithms
- APSP on Sparse Undirected Graphs with Arbitrary Weights
SUU
Sparse, Undirected, Unweighted
In this case, the graph $G=(V,E)$ that we consider is sparse ( $m = O(n)$ ), is undirected, and is unweighted (or equivalently, has all unit weights).
1 Algorithms
- APSP on Sparse Undirected Unweighted Graphs
- (5/3)-approximate ap-shortest paths
- APSP on Dense Directed Unweighted Graphs
- APSP on Directed Graphs with Real-Valued Weights
- APSP on Sparse Directed Graphs with Arbitrary Weights
- APSP on Sparse Directed Unweighted Graphs

DUA

Dense, Undirected, Arbitrary Weight

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

1 Algorithms

APSP on Dense Undirected Graphs with Positive Integer Weights

SUP

Sparse, Undirected, Positive Integer Weight

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

1 Algorithms

APSP on Sparse Undirected Graphs with Positive Integer Weights

Approximate Distance Oracle

Directed, Weighted APSP

Undirected, Weighted APSP