Package org.jgrapht.alg.shortestpath
Class BidirectionalDijkstraShortestPath<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
-
- org.jgrapht.alg.shortestpath.BidirectionalDijkstraShortestPath<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
ShortestPathAlgorithm<V,E>
public final class BidirectionalDijkstraShortestPath<V,E> extends BaseShortestPathAlgorithm<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.
- Since:
- July 2016
- See Also:
DijkstraShortestPath
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) class
BidirectionalDijkstraShortestPath.DirectedSpecifics
(package private) class
BidirectionalDijkstraShortestPath.QueueEntry
(package private) class
BidirectionalDijkstraShortestPath.SearchFrontier
Helper class to maintain the search frontier(package private) class
BidirectionalDijkstraShortestPath.Specifics
(package private) class
BidirectionalDijkstraShortestPath.UndirectedSpecifics
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,E>
-
-
Field Summary
Fields Modifier and Type Field Description private double
radius
-
Fields inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
graph
-
-
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.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private GraphPath<V,E>
createPath(BidirectionalDijkstraShortestPath.SearchFrontier forwardFrontier, BidirectionalDijkstraShortestPath.SearchFrontier backwardFrontier, double weight, V source, V commonVertex, V sink)
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 org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
createEmptyPath, getPaths, getPathWeight
-
-
-
-
Method Detail
-
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 vertexsink
- the target vertex- Returns:
- a shortest path or null if no path exists
-
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 typeE
- the graph edge type- Parameters:
graph
- the graph to be searchedsource
- the vertex at which the path should startsink
- the vertex at which the path should end- Returns:
- a shortest path, or null if no path exists
-
createPath
private GraphPath<V,E> createPath(BidirectionalDijkstraShortestPath.SearchFrontier forwardFrontier, BidirectionalDijkstraShortestPath.SearchFrontier backwardFrontier, double weight, V source, V commonVertex, V sink)
-
-