edu.princeton.cs.algs4

## Class DijkstraUndirectedSP

• Object
• edu.princeton.cs.algs4.DijkstraUndirectedSP

• ```public class DijkstraUndirectedSP
extends Object```
The `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.

Author:
Robert Sedgewick, Kevin Wayne, Nate Liu
• ### Constructor Summary

Constructors
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`.
• ### Method Summary

All Methods
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`.
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### DijkstraUndirectedSP

```public 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`.
Parameters:
`G` - the edge-weighted digraph
`s` - the source vertex
Throws:
`IllegalArgumentException` - if an edge weight is negative
`IllegalArgumentException` - unless `0 <= s < V`
• ### Method Detail

• #### distTo

`public double distTo(int v)`
Returns the length of a shortest path between the source vertex `s` and vertex `v`.
Parameters:
`v` - the destination vertex
Returns:
the length of a shortest path between the source vertex `s` and the vertex `v`; `Double.POSITIVE_INFINITY` if no such path
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• #### hasPathTo

`public boolean hasPathTo(int v)`
Returns true if there is a path between the source vertex `s` and vertex `v`.
Parameters:
`v` - the destination vertex
Returns:
`true` if there is a path between the source vertex `s` to vertex `v`; `false` otherwise
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• #### pathTo

`public Iterable<Edge> pathTo(int v)`
Returns a shortest path between the source vertex `s` and vertex `v`.
Parameters:
`v` - the destination vertex
Returns:
a shortest path between the source vertex `s` and vertex `v`; `null` if no such path
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• #### main

`public static void main(String[] args)`
Unit tests the `DijkstraUndirectedSP` data type.
Parameters:
`args` - the command-line arguments