edu.princeton.cs.algs4

## Class FloydWarshall

• Object
• edu.princeton.cs.algs4.FloydWarshall

• ```public class FloydWarshall
extends Object```
The `FloydWarshall` class represents a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs with no negative cycles. The edge weights can be positive, negative, or zero. This class finds either a shortest path between every pair of vertices or a negative cycle.

This implementation uses the Floyd-Warshall algorithm. The constructor takes Θ(V3) time, where V is the number of vertices. Each instance method takes Θ(1) time. It uses Θ(V2) extra space (not including the edge-weighted digraph).

This correctly computes shortest paths if all arithmetic performed is without floating-point rounding error or arithmetic overflow. This is the case if all edge weights are integers and if none of the intermediate results exceeds 252. Since all intermediate results are sums of edge weights, they are bounded by V C, where V is the number of vertices and C is the maximum absolute value of any edge weight.

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
`FloydWarshall(AdjMatrixEdgeWeightedDigraph 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` `hasNegativeCycle()`
Is there a negative cycle?
`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 `FloydWarshall` data type.
`Iterable<DirectedEdge>` `negativeCycle()`
Returns a negative cycle, or `null` if there is no such cycle.
`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

• #### FloydWarshall

`public FloydWarshall(AdjMatrixEdgeWeightedDigraph G)`
Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph `G`. If no such shortest path exists for some pair of vertices, it computes a negative cycle.
Parameters:
`G` - the edge-weighted digraph
• ### Method Detail

• #### hasNegativeCycle

`public boolean hasNegativeCycle()`
Is there a negative cycle?
Returns:
`true` if there is a negative cycle, and `false` otherwise
• #### negativeCycle

`public Iterable<DirectedEdge> negativeCycle()`
Returns a negative cycle, or `null` if there is no such cycle.
Returns:
a negative cycle as an iterable of edges, or `null` if there is no such cycle
• #### 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:
`UnsupportedOperationException` - if there is a negative cost cycle
`IllegalArgumentException` - unless `0 <= v < V`
• #### 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:
`UnsupportedOperationException` - if there is a negative cost cycle
`IllegalArgumentException` - unless `0 <= v < V`
• #### main

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