edu.princeton.cs.algs4

Class DijkstraSP

Object

edu.princeton.cs.algs4.DijkstraSP

public class DijkstraSP
extends Object

The DijkstraSP class represents a data type for solving the single-source shortest paths problem in edge-weighted digraphs 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 digraph).

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.

For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

Constructor and Description
DijkstraSP(EdgeWeightedDigraph G, int s) Computes a shortest-paths tree from the source vertex s to every other vertex in the edge-weighted digraph G.

Method Summary

Modifier and Type	Method and Description
double	distTo(int v) Returns the length of a shortest path from the source vertex s to vertex v.
boolean	hasPathTo(int v) Returns true if there is a path from the source vertex s to vertex v.
static void	main(String[] args) Unit tests the DijkstraSP data type.
Iterable<DirectedEdge>	pathTo(int v) Returns a shortest path from the source vertex s to vertex v.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DijkstraSP

public DijkstraSP(EdgeWeightedDigraph G,
                  int s)

Computes a shortest-paths tree from the source vertex s to every other vertex in the edge-weighted digraph 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 from the source vertex s to vertex v.

Parameters:

v - the destination vertex

Returns:

the length of a shortest path from the source vertex s to 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 from the source vertex s to vertex v.

Parameters:

v - the destination vertex

Returns:

true if there is a path from the source vertex s to vertex v; false otherwise

Throws:

IllegalArgumentException - unless 0 <= v < V

pathTo

public Iterable<DirectedEdge> pathTo(int v)

Returns a shortest path from the source vertex s to vertex v.

Parameters:

v - the destination vertex

Returns:

a shortest path from the source vertex s to vertex v as an iterable of edges, and null if no such path

Throws:

IllegalArgumentException - unless 0 <= v < V

main

public static void main(String[] args)

Unit tests the DijkstraSP data type.

Parameters:

args - the command-line arguments