Package org.graph4j.shortestpath

Class BFSSinglePairShortestPath

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.shortestpath.BFSSinglePairShortestPath

All Implemented Interfaces:

SinglePairShortestPath

public class BFSSinglePairShortestPath
extends GraphAlgorithm
implements SinglePairShortestPath

Determines the path with the fewest edges connecting two vertices. For unweighted graphs, breadth-first search can be used to find the shortest path between two vertices.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
BFSSinglePairShortestPath(Graph graph, int source, int target)	Creates an algorithm to find the path with the fewest edges between two specified vertices.
BFSSinglePairShortestPath(Graph graph, int source, int target, int[] forbiddenVertices)	Creates an algorithm to find the path with the fewest edges between two specified vertices, not passing through some forbidden vertices.

Method Summary

Modifier and Type	Method	Description
Path	findPath()	Returns the shortest path between source and target.
double	getPathWeight()	Returns the weight of the shortest path from the source to the target, or Double.POSITIVE_INFINITY if no path exists.
int	getSource()	Returns the source vertex number.
int	getTarget()	Returns the target vertex number.

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.SinglePairShortestPath

getGraph

Constructor Details

BFSSinglePairShortestPath

public BFSSinglePairShortestPath(Graph graph,
 int source,
 int target)

Creates an algorithm to find the path with the fewest edges between two specified vertices. If the input graph has weights on its edges, they are ignored.

Parameters:

graph - the input graph.

source - the source vertex number.

target - the target vertex number.

BFSSinglePairShortestPath

public BFSSinglePairShortestPath(Graph graph,
 int source,
 int target,
 int[] forbiddenVertices)

Creates an algorithm to find the path with the fewest edges between two specified vertices, not passing through some forbidden vertices.

Parameters:

graph - the input graph.

source - the source vertex number.

target - the target vertex number.

forbiddenVertices - vertices that are not allowed in the path; can be null if there are no forbidden vertices.

Method Details

getSource

public int getSource()

Description copied from interface: SinglePairShortestPath

Returns the source vertex number.

Specified by:

getSource in interface SinglePairShortestPath

Returns:

the source vertex number.

getTarget

public int getTarget()

Description copied from interface: SinglePairShortestPath

Returns the target vertex number.

Specified by:

getTarget in interface SinglePairShortestPath

Returns:

the target vertex number.

findPath

public Path findPath()

Description copied from interface: SinglePairShortestPath

Returns the shortest path between source and target.

Specified by:

findPath in interface SinglePairShortestPath

Returns:

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

getPathWeight

public double getPathWeight()

Description copied from interface: SinglePairShortestPath

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

Specified by:

getPathWeight in interface SinglePairShortestPath

Returns:

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