edu.princeton.cs.algs4

Class AcyclicSP

java.lang.Object

edu.princeton.cs.algs4.AcyclicSP

public class AcyclicSP
extends java.lang.Object

The AcyclicSP class represents a data type for solving the single-source shortest paths problem in edge-weighted directed acyclic graphs (DAGs). The edge weights can be positive, negative, or zero.

This implementation uses a topological-sort based algorithm. The constructor takes time proportional to V + E, 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.

Constructor Summary

Constructors

Constructor and Description
AcyclicSP(EdgeWeightedDigraph G, int s) Computes a shortest paths tree from s to every other vertex in the directed acyclic graph 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(java.lang.String[] args) Unit tests the AcyclicSP data type.
java.lang.Iterable<DirectedEdge>	pathTo(int v) Returns a shortest path from the source vertex s to vertex v.

Methods inherited from class java.lang.Object

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

Constructor Detail

AcyclicSP

public AcyclicSP(EdgeWeightedDigraph G,
                 int s)

Computes a shortest paths tree from s to every other vertex in the directed acyclic graph G.

Parameters:

G - the acyclic digraph

s - the source vertex

Throws:

java.lang.IllegalArgumentException - if the digraph is not acyclic

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

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

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

Throws:

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

pathTo

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

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

main

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

Unit tests the AcyclicSP data type.

Parameters:

args - the command-line arguments