Class AStarBidirection
- All Implemented Interfaces:
EdgeToEdgeRoutingAlgorithm
,RoutingAlgorithm
- Direct Known Subclasses:
AlternativeRoute
See http://research.microsoft.com/apps/pubs/default.aspx?id=64511 http://i11www.iti.uni-karlsruhe.de/_media/teaching/sommer2012/routenplanung/vorlesung4.pdf http://research.microsoft.com/pubs/64504/goldberg-sofsem07.pdf http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf
and
1. Ikeda, T., Hsu, M.-Y., Imai, H., Nishimura, S., Shimoura, H., Hashimoto, T., Tenmoku, K., and Mitoh, K. (1994). A fast algorithm for finding better routes by ai search techniques. In VNIS, pages 291–296.
2. Whangbo, T. K. (2007). Efficient modified bidirectional a* algorithm for optimal route- finding. In IEA/AIE, volume 4570, pages 344–353. Springer.
or could we even use this three phase approach? www.lix.polytechnique.fr/~giacomon/papers/bidirtimedep.pdf
- Author:
- Peter Karich, jansoe
-
Field Summary
Fields inherited from class com.graphhopper.routing.AbstractNonCHBidirAlgo
additionalEdgeFilter, edgeExplorer, graph, nodeAccess, weighting
Fields inherited from class com.graphhopper.routing.AbstractBidirAlgo
bestBwdEntry, bestFwdEntry, bestWeight, bestWeightMapFrom, bestWeightMapOther, bestWeightMapTo, currFrom, currTo, finishedFrom, finishedTo, from, fromOutEdge, maxVisitedNodes, timeoutMillis, to, toInEdge, traversalMode, updateBestPath
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected double
calcWeight
(EdgeIteratorState iter, SPTEntry currEdge, boolean reverse) protected SPTEntry
createEntry
(EdgeIteratorState edge, double weight, SPTEntry parent, boolean reverse) Creates a new entry of the shortest path tree (aSPTEntry
or one of its subclasses) during a dijkstra expansion.protected SPTEntry
createStartEntry
(int node, double weight, boolean reverse) Creates the root shortest path tree entry for the forward or backward search.protected boolean
finished()
getName()
setApproximation
(WeightApproximator approx) Methods inherited from class com.graphhopper.routing.AbstractNonCHBidirAlgo
accept, createEmptyPath, createPathExtractor, extractPath, fillEdgesFromUsingFilter, fillEdgesToUsingFilter, getInEdgeWeight, postInitFrom, postInitTo, toString
Methods inherited from class com.graphhopper.routing.AbstractBidirAlgo
bwdSearchCanBeStopped, calcPath, calcPath, calcPaths, checkAlreadyRun, fromEntryCanBeSkipped, fwdSearchCanBeStopped, getCurrentFromWeight, getCurrentToWeight, getIncomingEdge, getVisitedNodes, initCollections, initFrom, initTo, isMaxVisitedNodesExceeded, isTimeoutExceeded, postInit, runAlgo, setMaxVisitedNodes, setTimeoutMillis, setUpdateBestPath, setupFinishTime, toEntryCanBeSkipped, updateBestPath
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface com.graphhopper.routing.EdgeToEdgeRoutingAlgorithm
calcPath
Methods inherited from interface com.graphhopper.routing.RoutingAlgorithm
calcPath, calcPaths, getVisitedNodes, setMaxVisitedNodes, setTimeoutMillis
-
Constructor Details
-
AStarBidirection
-
-
Method Details
-
finished
protected boolean finished()- Overrides:
finished
in classAbstractBidirAlgo
-
createStartEntry
Description copied from class:AbstractBidirAlgo
Creates the root shortest path tree entry for the forward or backward search.- Specified by:
createStartEntry
in classAbstractBidirAlgo
-
createEntry
protected SPTEntry createEntry(EdgeIteratorState edge, double weight, SPTEntry parent, boolean reverse) Description copied from class:AbstractNonCHBidirAlgo
Creates a new entry of the shortest path tree (aSPTEntry
or one of its subclasses) during a dijkstra expansion.- Specified by:
createEntry
in classAbstractNonCHBidirAlgo
- Parameters:
edge
- the edge that is currently processed for the expansionweight
- the weight the shortest path three entry should carryparent
- the parent entry of in the shortest path treereverse
- true if we are currently looking at the backward search, false otherwise
-
calcWeight
- Overrides:
calcWeight
in classAbstractNonCHBidirAlgo
-
getApproximation
-
setApproximation
-
getName
- Specified by:
getName
in interfaceRoutingAlgorithm
- Overrides:
getName
in classAbstractBidirAlgo
- Returns:
- name of this algorithm
-