Package edu.princeton.cs.algs4

Class AcyclicSP

Object

edu.princeton.cs.algs4.AcyclicSP

public class AcyclicSP
extends 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 Θ(V + E) 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 absolute value of any edge weight.

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

IllegalArgumentException - if the digraph is not acyclic

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)

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:

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 AcyclicSP data type.

Parameters:

args - the command-line arguments