edu.princeton.cs.algs4

• Object

• ```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 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 V2, 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.

Author:
Robert Sedgewick, 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

Methods
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`?
`Iterable<DirectedEdge>` ```path(int s, int t)```
Returns a shortest path from vertex `s` to vertex `t`.
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

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