Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
Class BaseBidirectionalShortestPathAlgorithm<V,E>
java.lang.Object
org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm<V,E>
- Type Parameters:
V
- vertices typeE
- edges type
- All Implemented Interfaces:
ShortestPathAlgorithm<V,
E>
- Direct Known Subclasses:
BidirectionalAStarShortestPath
,BidirectionalDijkstraShortestPath
public abstract class BaseBidirectionalShortestPathAlgorithm<V,E>
extends BaseShortestPathAlgorithm<V,E>
Base class for the bidirectional shortest path algorithms. Currently known extensions are
BidirectionalDijkstraShortestPath
and BidirectionalAStarShortestPath
.-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) static class
Base class of the search frontier used by bidirectional shortest path algorithms.Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,
E> -
Field Summary
Fields inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
graph, GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE, GRAPH_MUST_CONTAIN_THE_SINK_VERTEX, GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
-
Constructor Summary
ConstructorsConstructorDescriptionConstructs a new instance of the algorithm for a given graph. -
Method Summary
Modifier and TypeMethodDescriptioncreatePath
(BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V, E> forwardFrontier, BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V, E> backwardFrontier, double weight, V source, V commonVertex, V sink) Builds shortest path betweensource
andsink
based on the information provided by search frontiers and common vertex.Methods inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
createEmptyPath, getPaths, getPathWeight
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
getPath
-
Constructor Details
-
BaseBidirectionalShortestPathAlgorithm
Constructs a new instance of the algorithm for a given graph.- Parameters:
graph
- the graph
-
-
Method Details
-
createPath
protected GraphPath<V,E> createPath(BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V, E> forwardFrontier, BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V, E> backwardFrontier, double weight, V source, V commonVertex, V sink) Builds shortest path betweensource
andsink
based on the information provided by search frontiers and common vertex.- Parameters:
forwardFrontier
- forward direction frontierbackwardFrontier
- backward direction frontierweight
- weight of the shortest pathsource
- path sourcecommonVertex
- path common vertexsink
- path sink- Returns:
- shortest path between source and sink
-