AStar.H File Reference

A* shortest path algorithm. More...

#include <cmath>
#include <iostream>
#include <ahFunction.H>
#include <ah-errors.H>
#include <archeap.H>
#include <tpl_find_path.H>
#include <tpl_agraph.H>
#include <shortest_path_common.H>

Include dependency graph for AStar.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Zero_Heuristic< GT, Distance >
	Default heuristic for A* (zero heuristic, degrades to Dijkstra). More...
class	Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >
	A* algorithm for finding the shortest path between two nodes. More...
struct	Aleph::Euclidean_Heuristic< GT, Distance >
	Euclidean distance heuristic for A* in 2D grids. More...
struct	Aleph::Manhattan_Heuristic< GT, Distance >
	Manhattan distance heuristic for A* in grid graphs. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Macros
#define	ANassert(p)   (static_cast<Node_Info*>(NODE_COOKIE(p)))
#define	ATREENODE(p)   (static_cast<Tree_Node_Info*>(NODE_COOKIE(p))->tree_node)
#define	AACC(p)   (ANassert(p)->dist)
#define	AHEAPNODE(p)   (ANassert(p)->heap_node)
#define	APARENT(p)   (ANassert(p)->ret_node)
#define	AAassert(p)   (static_cast<Arc_Info*>(ARC_COOKIE(p)))
#define	AARC_DIST(p)   (Distance()(p))
#define	ATREEARC(p)   (static_cast<Tree_Arc_Info*>(ARC_COOKIE(p))->tree_arc)
#define	APOT(p)   (AAassert(p)->pot)

Detailed Description

A* shortest path algorithm.

Implements the A* algorithm for finding the shortest path between two vertices in a weighted graph using a heuristic function. The algorithm uses f(n) = g(n) + h(n) where g(n) is the cost from start and h(n) is the heuristic estimate to the goal. Uses binary heap for O((V+E)log V).

The heuristic must be admissible (never overestimate) for optimal paths.

When no goal is specified (e.g., compute_min_paths_tree), the algorithm behaves like Dijkstra's algorithm (zero heuristic).

Author

Leandro Rabindranath León

Definition in file AStar.H.

Macro Definition Documentation

AAassert

#define AAassert

(

p

)

(static_cast<Arc_Info*>(ARC_COOKIE(p)))

Definition at line 180 of file AStar.H.

AACC

#define AACC

(

p

)

(ANassert(p)->dist)

Definition at line 177 of file AStar.H.

AARC_DIST

#define AARC_DIST

(

p

)

(Distance()(p))

Definition at line 181 of file AStar.H.

AHEAPNODE

#define AHEAPNODE

(

p

)

(ANassert(p)->heap_node)

Definition at line 178 of file AStar.H.

ANassert

#define ANassert

(

p

)

(static_cast<Node_Info*>(NODE_COOKIE(p)))

Definition at line 175 of file AStar.H.

APARENT

#define APARENT

(

p

)

(ANassert(p)->ret_node)

Definition at line 179 of file AStar.H.

APOT

#define APOT

(

p

)

(AAassert(p)->pot)

Definition at line 183 of file AStar.H.

ATREEARC

#define ATREEARC

(

p

)

(static_cast<Tree_Arc_Info*>(ARC_COOKIE(p))->tree_arc)

Definition at line 182 of file AStar.H.

ATREENODE

#define ATREENODE

(

p

)

(static_cast<Tree_Node_Info*>(NODE_COOKIE(p))->tree_node)

Definition at line 176 of file AStar.H.