Class BidirectionalDijkstraShortestPath<V,E>

java.lang.Object

org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>

org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm<V,E>

org.jgrapht.alg.shortestpath.BidirectionalDijkstraShortestPath<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

ShortestPathAlgorithm<V,E>

public final class BidirectionalDijkstraShortestPath<V,E>
extends BaseBidirectionalShortestPathAlgorithm<V,E>

A bidirectional version of Dijkstra's algorithm.

See the Wikipedia article for details and references about bidirectional search. This technique does not change the worst-case behavior of the algorithm but reduces, in some cases, the number of visited vertices in practice. This implementation alternatively constructs forward and reverse paths from the source and target vertices respectively.

This iterator can use a custom heap implementation, which can specified during the construction time. Pairing heap is used by default

See Also:

• DijkstraShortestPath

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
(package private) static class	BidirectionalDijkstraShortestPath.DijkstraSearchFrontier<V,E>	Maintains search frontier during shortest path computation.

Nested classes/interfaces inherited from class BaseBidirectionalShortestPathAlgorithm

BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V,E>

Nested classes/interfaces inherited from interface ShortestPathAlgorithm

ShortestPathAlgorithm.SingleSourcePaths<V,E>

Field Summary

Fields

Modifier and Type	Field	Description
private final Supplier<org.jheaps.AddressableHeap<Double, Pair<V,E>>>	heapSupplier
private double	radius

Fields inherited from class BaseShortestPathAlgorithm

graph, GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE, GRAPH_MUST_CONTAIN_THE_SINK_VERTEX, GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

Constructor Summary

Constructors

Constructor	Description
BidirectionalDijkstraShortestPath(Graph<V,E> graph)	Constructs a new instance for a specified graph.
BidirectionalDijkstraShortestPath(Graph<V,E> graph, double radius)	Constructs a new instance for a specified graph.
BidirectionalDijkstraShortestPath(Graph<V,E> graph, double radius, Supplier<org.jheaps.AddressableHeap<Double, Pair<V,E>>> heapSupplier)	Constructs a new instance for a specified graph.
BidirectionalDijkstraShortestPath(Graph<V,E> graph, Supplier<org.jheaps.AddressableHeap<Double, Pair<V,E>>> heapSupplier)	Constructs a new instance for a specified graph.

Method Summary

Modifier and Type	Method	Description
static <V,E> GraphPath<V,E>	findPathBetween(Graph<V,E> graph, V source, V sink)	Find a path between two vertices.
GraphPath<V,E>	getPath(V source, V sink)	Get a shortest path from a source vertex to a sink vertex.

Methods inherited from class BaseBidirectionalShortestPathAlgorithm

createPath

Methods inherited from class BaseShortestPathAlgorithm

createEmptyPath, getPaths, getPathWeight

Methods inherited from class Object

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

Field Details

radius

private double radius

heapSupplier

private final Supplier<org.jheaps.AddressableHeap<Double, Pair<V,E>>> heapSupplier

Constructor Details

BidirectionalDijkstraShortestPath

public BidirectionalDijkstraShortestPath(Graph<V,E> graph)

Constructs a new instance for a specified graph.

Parameters:

graph - the input graph

BidirectionalDijkstraShortestPath

public BidirectionalDijkstraShortestPath(Graph<V,E> graph,
 Supplier<org.jheaps.AddressableHeap<Double, Pair<V,E>>> heapSupplier)

Constructs a new instance for a specified graph. The constructed algorithm will use the heap supplied by the heapSupplier.

Parameters:

graph - the input graph

heapSupplier - supplier of the preferable heap implementation

BidirectionalDijkstraShortestPath

public BidirectionalDijkstraShortestPath(Graph<V,E> graph,
 double radius)

Constructs a new instance for a specified graph.

Parameters:

graph - the input graph

radius - limit on path length, or Double.POSITIVE_INFINITY for unbounded search

BidirectionalDijkstraShortestPath

public BidirectionalDijkstraShortestPath(Graph<V,E> graph,
 double radius,
 Supplier<org.jheaps.AddressableHeap<Double, Pair<V,E>>> heapSupplier)

Constructs a new instance for a specified graph. The constructed algorithm will use the heap supplied by the heapSupplier.

Parameters:

graph - the input graph

radius - limit on path length, or Double.POSITIVE_INFINITY for unbounded search

heapSupplier - supplier of the preferable heap implementation

Method Details

findPathBetween

public static <V,E> GraphPath<V,E> findPathBetween(Graph<V,E> graph,
 V source,
 V sink)

Find a path between two vertices. For a more advanced search (e.g. limited by radius), use the constructor instead.

Type Parameters:

V - the graph vertex type

E - the graph edge type

Parameters:

graph - the graph to be searched

source - the vertex at which the path should start

sink - the vertex at which the path should end

Returns:

a shortest path, or null if no path exists

getPath

public GraphPath<V,E> getPath(V source,
 V sink)

Description copied from interface: ShortestPathAlgorithm

Get a shortest path from a source vertex to a sink vertex.

Parameters:

source - the source vertex

sink - the target vertex

Returns:

a shortest path or null if no path exists