Package org.graph4j.shortestpath

Class BidirectionalDijkstra

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.shortestpath.BidirectionalDijkstra

All Implemented Interfaces:

SinglePairShortestPath

public class BidirectionalDijkstra
extends GraphAlgorithm
implements SinglePairShortestPath

Determines the shortest path between two vertices. Performs a forward search starting from a source vertex and a reverse (backward) search on the transpose graph starting from the target vertex.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
BidirectionalDijkstra(Graph graph, int source, int target)	Creates an algorithm to find the shortest path between source and target.

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

BidirectionalDijkstra

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

Creates an algorithm to find the shortest path between source and target.

Parameters:

graph - the input graph.

source - the source vertex number.

target - the target vertex number.

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.