public class DijkstraSP extends Object
DijkstraSP
class represents a data type for solving the
single-source shortest paths problem in edge-weighted digraphs
where the edge weights are non-negative.
This implementation uses Dijkstra's algorithm with a binary heap. The constructor takes Θ(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 Θ(V) extra space (not including the edge-weighted digraph).
This correctly computes shortest paths if all arithmetic performed is without floating-point rounding error or arithmetic overflow. This is the case if all edge weights are integers and if none of the intermediate results exceeds 252. Since all intermediate results are sums of edge weights, they are bounded by V C, where V is the number of vertices and C is the maximum weight of any edge.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
DijkstraSP(EdgeWeightedDigraph G,
int s)
Computes a shortest-paths tree from the source vertex
s to every other
vertex in the edge-weighted digraph G . |
Modifier and Type | Method and Description |
---|---|
double |
distTo(int v)
Returns the length of a shortest path from the source vertex
s to vertex v . |
boolean |
hasPathTo(int v)
Returns true if there is a path from the source vertex
s to vertex v . |
static void |
main(String[] args)
Unit tests the
DijkstraSP data type. |
Iterable<DirectedEdge> |
pathTo(int v)
Returns a shortest path from the source vertex
s to vertex v . |
public DijkstraSP(EdgeWeightedDigraph G, int s)
s
to every other
vertex in the edge-weighted digraph G
.G
- the edge-weighted digraphs
- the source vertexIllegalArgumentException
- if an edge weight is negativeIllegalArgumentException
- unless 0 <= s < V
public double distTo(int v)
s
to vertex v
.v
- the destination vertexs
to vertex v
;
Double.POSITIVE_INFINITY
if no such pathIllegalArgumentException
- unless 0 <= v < V
public boolean hasPathTo(int v)
s
to vertex v
.v
- the destination vertextrue
if there is a path from the source vertex
s
to vertex v
; false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public Iterable<DirectedEdge> pathTo(int v)
s
to vertex v
.v
- the destination vertexs
to vertex v
as an iterable of edges, and null
if no such pathIllegalArgumentException
- unless 0 <= v < V
public static void main(String[] args)
DijkstraSP
data type.args
- the command-line arguments