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

All Methods
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

`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