Package org.graph4j.shortestpath

Class FloydWarshallShortestPath

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.shortestpath.FloydWarshallShortestPath

All Implemented Interfaces:

AllPairsShortestPath

public class FloydWarshallShortestPath
extends GraphAlgorithm
implements AllPairsShortestPath

Floyd-Warshall's algorithm finds the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It has a complexity of O(n^3). It is best suited for dense graphs. In case of sparse graphs JohnsonShortestPath algorithm may perform better.

Author:

Cristian Frăsinaru

See Also:

• JohnsonShortestPath

Field Summary

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
FloydWarshallShortestPath(Graph graph)

Method Summary

Modifier and Type	Method	Description
Path	findPath(int source, int target)	Returns the shortest path between source and target.
double	getPathWeight(int source, int target)
double[][]	getPathWeights()	Returns a matrix containing the weights of the shortest paths for every pair of vertices.

Methods inherited from class org.graph4j.GraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.graph4j.shortestpath.AllPairsShortestPath

getGraph

Constructor Details

FloydWarshallShortestPath

public FloydWarshallShortestPath(Graph graph)

Method Details

findPath

public Path findPath(int source,
 int target)

Description copied from interface: AllPairsShortestPath

Returns the shortest path between source and target. On the first invocation of this method, it computes shortest paths between any two vertices of the graph, then it returns the requested one. All the shortest paths are stored for later retrieval, so subsequent invocations will return the already computed paths.

Specified by:

findPath in interface AllPairsShortestPath

Parameters:

source - the number of the source vertex.

target - the number of the target vertex.

Returns:

the shortest path from the source to the target, or null if no path exists.

getPathWeight

public double getPathWeight(int source,
 int target)

Specified by:

getPathWeight in interface AllPairsShortestPath

Parameters:

source - the number of the source vertex.

target - the number of the target vertex.

Returns:

the weight of the shortest path from the source to the target, or Double.POSTIVE_INFINITY if no path exists.

getPathWeights

public double[][] getPathWeights()

Description copied from interface: AllPairsShortestPath

Returns a matrix containing the weights of the shortest paths for every pair of vertices.

Specified by:

getPathWeights in interface AllPairsShortestPath

Returns:

a matrix containing the weights of the shortest paths for every pair of vertices.