edu.princeton.cs.algs4

Class DijkstraAllPairsSP

java.lang.Object

edu.princeton.cs.algs4.DijkstraAllPairsSP

public class DijkstraAllPairsSP
extends java.lang.Object

The DijkstraAllPairsSP class represents a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs where the edge weights are nonnegative.

This implementation runs Dijkstra's algorithm from each vertex. The constructor takes time proportional to V (E log V) and uses space proprtional to V², where V is the number of vertices and E is the number of edges. Afterwards, the dist() and hasPath() methods take constant time and the path() 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.

Constructor Summary

Constructors

Constructor and Description
DijkstraAllPairsSP(EdgeWeightedDigraph G) Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph G.

Method Summary

Modifier and Type	Method and Description
double	dist(int s, int t) Returns the length of a shortest path from vertex s to vertex t.
boolean	hasPath(int s, int t) Is there a path from the vertex s to vertex t?
java.lang.Iterable<DirectedEdge>	path(int s, int t) Returns a shortest path from vertex s to vertex t.

Methods inherited from class java.lang.Object

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

Constructor Detail

DijkstraAllPairsSP

public DijkstraAllPairsSP(EdgeWeightedDigraph G)

Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph G.

Parameters:

G - the edge-weighted digraph

Throws:

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

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

Method Detail

path

public java.lang.Iterable<DirectedEdge> path(int s,
                                             int t)

Returns a shortest path from vertex s to vertex t.

Parameters:

s - the source vertex

t - the destination vertex

Returns:

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

Throws:

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

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

hasPath

public boolean hasPath(int s,
                       int t)

Is there a path from the vertex s to vertex t?

Parameters:

s - the source vertex

t - the destination vertex

Returns:

true if there is a path from vertex s to vertex t, and false otherwise

Throws:

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

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

dist

public double dist(int s,
                   int t)

Returns the length of a shortest path from vertex s to vertex t.

Parameters:

s - the source vertex

t - the destination vertex

Returns:

the length of a shortest path from vertex s to vertex t; Double.POSITIVE_INFINITY if no such path

Throws:

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

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