edu.princeton.cs.algs4

Class DijkstraUndirectedSP

java.lang.Object

edu.princeton.cs.algs4.DijkstraUndirectedSP

public class DijkstraUndirectedSP
extends java.lang.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 nonnegative.

This implementation uses Dijkstra's algorithm with a binary heap. The constructor takes time proportional to E log V, where V is the number of vertices and E is the number of edges. Each call to distTo(int) and hasPathTo(int) takes constant time; each call to pathTo(int) takes time proportional to the number of edges in the shortest path returned.

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.

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(java.lang.String[] args) Unit tests the DijkstraUndirectedSP data type.
java.lang.Iterable<Edge>	pathTo(int v) Returns a shortest path between the source vertex s and vertex v.

Methods inherited from class java.lang.Object

equals, 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:

java.lang.IllegalArgumentException - if an edge weight is negative

java.lang.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:

java.lang.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:

java.lang.IllegalArgumentException - unless 0 <= v < V

pathTo

public java.lang.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:

java.lang.IllegalArgumentException - unless 0 <= v < V

main

public static void main(java.lang.String[] args)

Unit tests the DijkstraUndirectedSP data type.

Parameters:

args - the command-line arguments