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 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.
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