Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
Class BaseBidirectionalShortestPathAlgorithm<V,E>
java.lang.Object
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
Base class for the bidirectional shortest path algorithms. Currently known extensions are
BidirectionalDijkstraShortestPath
and BidirectionalAStarShortestPath
.- Author:
- Dimitrios Michail
-
Nested Class Summary
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,
E> -
Field Summary
Modifier and TypeFieldDescriptionThe underlying graph.protected static final String
Error message for reporting the existence of a negative-weight cycle.protected static final String
Error message for reporting that a sink vertex is missing.protected static final String
Error message for reporting that a source vertex is missing. -
Constructor Summary
ConstructorDescriptionConstructs a new instance of the algorithm for a given graph. -
Method Summary
Modifier and TypeMethodDescriptioncreateEmptyPath
(V source, V sink) Create an empty path.createPath
(org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V, E> forwardFrontier, org.jgrapht.alg.shortestpath.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.Compute all shortest paths starting from a single source vertex.double
getPathWeight
(V source, V sink) Get the weight of the shortest path from a source vertex to a sink vertex.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
-
Field Details
-
GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negative-weight cycle.- See Also:
-
GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing.- See Also:
-
GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing.- See Also:
-
graph
The underlying graph.
-
-
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(org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V, E> forwardFrontier, org.jgrapht.alg.shortestpath.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
-
getPaths
Compute all shortest paths starting from a single source vertex.- Specified by:
getPaths
in interfaceShortestPathAlgorithm<V,
E> - Parameters:
source
- the source vertex- Returns:
- the shortest paths
-
getPathWeight
Get the weight of the shortest path from a source vertex to a sink vertex. ReturnsDouble.POSITIVE_INFINITY
if no path exists.- Specified by:
getPathWeight
in interfaceShortestPathAlgorithm<V,
E> - Parameters:
source
- the source vertexsink
- the sink vertex- Returns:
- the weight of the shortest path from a source vertex to a sink vertex, or
Double.POSITIVE_INFINITY
if no path exists
-
createEmptyPath
Create an empty path. Returns null if the source vertex is different than the target vertex.- Parameters:
source
- the source vertexsink
- the sink vertex- Returns:
- an empty path or null null if the source vertex is different than the target vertex
-