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 2^{52}. 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