public class DijkstraUndirectedSP extends Object
DijkstraUndirectedSP
class represents a data type for solving
the single-source shortest paths problem in edge-weighted graphs
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 graph).
For additional documentation,
see Section 4.4 of
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
See DijkstraSP
for a version on edge-weighted digraphs.
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.
Constructor and Description |
---|
DijkstraUndirectedSP(EdgeWeightedGraph G,
int s)
Computes a shortest-paths tree from the source vertex
s to every
other vertex in the edge-weighted graph G . |
Modifier and Type | Method and Description |
---|---|
double |
distTo(int v)
Returns the length of a shortest path between the source vertex
s and
vertex v . |
boolean |
hasPathTo(int v)
Returns true if there is a path between the source vertex
s and
vertex v . |
static void |
main(String[] args)
Unit tests the
DijkstraUndirectedSP data type. |
Iterable<Edge> |
pathTo(int v)
Returns a shortest path between the source vertex
s and vertex v . |
public DijkstraUndirectedSP(EdgeWeightedGraph G, int s)
s
to every
other vertex in the edge-weighted graph 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
and
vertex v
.v
- the destination vertexs
and
the vertex v
; Double.POSITIVE_INFINITY
if no such pathIllegalArgumentException
- unless 0 <= v < V
public boolean hasPathTo(int v)
s
and
vertex v
.v
- the destination vertextrue
if there is a path between the source vertex
s
to vertex v
; false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public Iterable<Edge> pathTo(int v)
s
and vertex v
.v
- the destination vertexs
and vertex v
;
null
if no such pathIllegalArgumentException
- unless 0 <= v < V
public static void main(String[] args)
DijkstraUndirectedSP
data type.args
- the command-line arguments