Package org.graph4j.shortestpath

Class BFSAllPairsShortestPath

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.shortestpath.BFSAllPairsShortestPath

All Implemented Interfaces:

AllPairsShortestPath

public class BFSAllPairsShortestPath
extends GraphAlgorithm
implements AllPairsShortestPath

Determines the shortest paths between all pairs of vertices, in an unweighted graph, using breadth-first traversals.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
BFSAllPairsShortestPath(Graph graph)	Creates an algorithm for finding all pair shortest paths in an unweighted 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

BFSAllPairsShortestPath

public BFSAllPairsShortestPath(Graph graph)

Creates an algorithm for finding all pair shortest paths in an unweighted graph. If the input graph has weights on its edges, they are ignored.

Parameters:

graph - the input 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.