abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
AStar< GR , LEN , HM , TR > Class Template Reference

A* algorithm for a shortest path between two nodes. More...

#include <lemon/astar.h>

Classes

struct  SetHeap
 Named parameter for setting the type of the heap. More...

Public Types

typedef GR Digraph
 The digraph type of the algorithm.
typedef LEN LengthMap
 The type of the map of the arc lengths.
typedef HM HeuristicMap
 The type of the map of the heuristic values.
typedef LengthMap::Value Value
 The type of the lengths.
typedef lemon::Path< Digraph > Path
 The type of the shortest path.
typedef TR::HeapCrossRef HeapCrossRef
 The type of the cross reference map of the heap.
typedef TR::Heap Heap
 The type of the heap.

Public Member Functions

 AStar (const Digraph &graph, const LengthMap &length, const HeuristicMap &heuristic)
 Constructor.
bool run (const Node &s, const Node &t)
 Find a shortest path from s to t.
Query Functions

The results of the last run() that returned true.

Value dist () const
 Return the length of a shortest path.
const Path & path () const
 Return a shortest path, empty if the source is the target.
int scanned () const
 Return the number of scans of nodes, a node scanned again counted again.

Detailed Description

template< typename GR , typename LEN , typename HM , typename TR = AStarDefaultTraits< GR , LEN > >
class lemon::AStar< GR , LEN , HM , TR >

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
GRThe digraph type the algorithm runs on.
LENThe type of the map of the arc lengths, whose values must be nonnegative.
HMThe type of the map of the heuristic values of the nodes, whose value type is that of the lengths.
TRThe traits class, which gives the type of the heap [see AStarDefaultTraits and SetHeap].

Constructor & Destructor Documentation

◆ AStar()

template< typename GR , typename LEN , typename HM , typename TR = AStarDefaultTraits< GR , LEN > >
AStar ( const Digraph & graph,
const LengthMap & length,
const HeuristicMap & heuristic )
inline

Constructor.

Parameters
graphThe digraph the algorithm runs on.
lengthThe lengths of the arcs, which must be nonnegative.
heuristicThe 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.

Member Function Documentation

◆ run()

template< typename GR , typename LEN , typename HM , typename TR = AStarDefaultTraits< GR , LEN > >
bool run ( const Node & s,
const Node & t )
inline
Returns
true if t is reachable from s; its distance and a shortest path are then given by dist() and path().