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 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 Θ(V2) 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 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

All 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`?
`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 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`
• #### main

`public static void main(String[] args)`
Unit tests the `DijkstraAllPairsSP` data type.
Parameters:
`args` - the command-line arguments