Package edu.princeton.cs.algs4

Class DijkstraAllPairsSP

Object

edu.princeton.cs.algs4.DijkstraAllPairsSP

public class DijkstraAllPairsSP
extends 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 non-negative.

This implementation runs Dijkstra's algorithm from each vertex. The constructor takes Θ(V (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).

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
DijkstraAllPairsSP(EdgeWeightedDigraph G)	Computes a shortest paths tree from each vertex to every other vertex in the edge-weighted digraph G.

Method Summary

Modifier and Type	Method	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?
static void	main(String[] args)	Unit tests the DijkstraAllPairsSP data type.
Iterable<DirectedEdge>	path(int s, int t)	Returns a shortest path from vertex s to vertex t.

Methods inherited from class java.lang.Object

clone, 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 every other vertex in the edge-weighted digraph G.

Parameters:

G - the edge-weighted digraph

Throws:

IllegalArgumentException - if an edge weight is negative

IllegalArgumentException - unless 0 <= s < V

Method Detail

path

public 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:

IllegalArgumentException - unless 0 <= s < V

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:

IllegalArgumentException - unless 0 <= s < V

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:

IllegalArgumentException - unless 0 <= s < V

IllegalArgumentException - unless 0 <= t < V

main

public static void main(String[] args)

Unit tests the DijkstraAllPairsSP data type.

Parameters:

args - the command-line arguments