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 2⁵². 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

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