AStar
Declared in lemon/astar.h, in the group Shortest Path Algorithms; the same class on the Doxygen site.
-
template< typename GR , typename LEN , typename HM , typename TR = AStarDefaultTraits< GR , LEN > >
class AStar A* algorithm for a shortest path between two nodes.
This class finds a shortest path from a source to a target node of a digraph with nonnegative arc lengths, by Dijkstra’s algorithm guided by a heuristic: the nodes are scanned in the order of their tentative distance from the source plus the heuristic value, an estimate of their distance to the target, and the search stops when the target is scanned. The heuristic must be admissible, i.e., \(h(v) - h(t) \leq \delta(v,t)\) for each node \(v\), where \(\delta(v,t)\) is the distance from \(v\) to the target \(t\): with \(h(t) = 0\), never larger than the distance to the target (e.g., the straight-line distance on a road network). The closer it is to that distance, the fewer nodes are scanned; with a heuristic that is everywhere zero, it is Dijkstra’s algorithm stopped at the target. A heuristic that is also consistent, i.e., for which \(h(u) \leq \ell(uv) + h(v)\) on every arc, scans each node at most once; with an admissible one that is not, a node whose distance improves after its scan is scanned again.
- Template Parameters:
GR – The digraph type the algorithm runs on.
LEN – The type of the map of the arc lengths, whose values must be nonnegative.
HM – The type of the map of the heuristic values of the nodes, whose value type is that of the lengths.
TR – The traits class, which gives the type of the heap [see AStarDefaultTraits and SetHeap].
Query Functions
The results of the last run() that returned
true.-
inline int scanned() const
Return the number of scans of nodes, a node scanned again counted again.
Public Types
Public Functions
- inline AStar(
- const Digraph & graph,
- const LengthMap & length,
- const HeuristicMap & heuristic
Constructor.
- Parameters:
graph – The digraph the algorithm runs on.
length – The lengths of the arcs, which must be nonnegative.
heuristic – The heuristic values of the nodes, which must not exceed their distances to the target of each run() by more than the value of that target.