public class DijkstraAllPairsSP extends Object
DijkstraAllPairsSP
class represents a data type for solving the
all-pairs shortest paths problem in edge-weighted digraphs
where the edge weights are non-negative.
This implementation runs Dijkstra's algorithm from each vertex. The constructor takes Θ(V (E log V)) time in the worst case, where V is the number of vertices and E is the number of edges. Each instance method takes Θ(1) time. It uses Θ(V2) extra space (not including the edge-weighted digraph).
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
DijkstraAllPairsSP(EdgeWeightedDigraph G)
Computes a shortest paths tree from each vertex to every other vertex in
the edge-weighted digraph
G . |
Modifier and Type | Method and Description |
---|---|
double |
dist(int s,
int t)
Returns the length of a shortest path from vertex
s to vertex t . |
boolean |
hasPath(int s,
int t)
Is there a path from the vertex
s to vertex t ? |
static void |
main(String[] args)
Unit tests the
DijkstraAllPairsSP data type. |
Iterable<DirectedEdge> |
path(int s,
int t)
Returns a shortest path from vertex
s to vertex t . |
public DijkstraAllPairsSP(EdgeWeightedDigraph G)
G
.G
- the edge-weighted digraphIllegalArgumentException
- if an edge weight is negativeIllegalArgumentException
- unless 0 <= s < V
public Iterable<DirectedEdge> path(int s, int t)
s
to vertex t
.s
- the source vertext
- the destination vertexs
to vertex t
as an iterable of edges, and null
if no such pathIllegalArgumentException
- unless 0 <= s < V
IllegalArgumentException
- unless 0 <= t < V
public boolean hasPath(int s, int t)
s
to vertex t
?s
- the source vertext
- the destination vertextrue
if there is a path from vertex s
to vertex t
, and false
otherwiseIllegalArgumentException
- unless 0 <= s < V
IllegalArgumentException
- unless 0 <= t < V
public double dist(int s, int t)
s
to vertex t
.s
- the source vertext
- the destination vertexs
to vertex t
;
Double.POSITIVE_INFINITY
if no such pathIllegalArgumentException
- unless 0 <= s < V
IllegalArgumentException
- unless 0 <= t < V
public static void main(String[] args)
DijkstraAllPairsSP
data type.args
- the command-line arguments