edu.princeton.cs.algorithms

Class DijkstraSP

java.lang.Object

edu.princeton.cs.algorithms.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 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. Afterwards, the distTo() and hasPathTo() methods take constant time and the pathTo() method 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.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

Constructor and Description
DijkstraSP(EdgeWeightedDigraph G, int s) Computes a shortest paths tree from 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) Is there 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 java.lang.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 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 - 1

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

hasPathTo

public boolean hasPathTo(int v)

Is there 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, and false otherwise

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

main

public static void main(String[] args)

Unit tests the DijkstraSP data type.