, source, weight, heuristic=<function <lambda>>, dist_map=None, combine=None, compare=None, zero=0, infinity=inf, array=False)[source]#

Return an iterator of the edges corresponding to an \(A^*\) traversal of the graph.


Graph to be used.


Source vertex.


Edge property map with weight values.

heuristicunary function (optional, default: lambda v: 1)

The heuristic function that guides the search. It should take a single argument which is a Vertex, and output an estimated distance from the supplied vertex to the target vertex.

dist_mapVertexPropertyMap (optional, default: None)

A vertex property map where the distances from the source will be stored.

combinebinary function (optional, default: lambda a, b: a + b)

This function is used to combine distances to compute the distance of a path.

comparebinary function (optional, default: lambda a, b: a < b)

This function is use to compare distances to determine which vertex is closer to the source vertex.

zeroint or float (optional, default: 0)

Value assumed to correspond to a distance of zero by the combine and compare functions.

infinityint or float (optional, default: numpy.inf)

Value assumed to correspond to a distance of infinity by the combine and compare functions.

arraybool (optional, default: False)

If True, a numpy.ndarray with the edge endpoints be returned instead.

astar_iteratorIterator or numpy.ndarray

An iterator over the edges in \(A^*\) order. If array == True, this will be a numpy.ndarray instead, of shape (E,2), containing the edge endpoints.

See also


Breadth-first search


Depth-first search


Dijkstra search algorithm


See astar_search() for an explanation of the algorithm.

The time complexity is \(O(1)\) to create the generator and \(O((E + V)\log V)\) to traverse it completely.



Hart, P. E.; Nilsson, N. J.; Raphael, B. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. IEEE Transactions on Systems Science and Cybernetics SSC4 4 (2): 100-107, 1968. DOI: 10.1109/TSSC.1968.300136 [sci-hub, @tor]


>>> g = gt.load_graph("search_example.xml")
>>> name = g.vp["name"]
>>> weight = g.ep["weight"]
>>> for e in gt.astar_iterator(g, g.vertex(0), weight):
...    print(name[e.source()], "->", name[])
Bob -> Eve
Bob -> Chuck
Bob -> Carlos
Bob -> Isaac
Eve -> Imothep
Eve -> Carol
Carlos -> Alice
Alice -> Oscar
Alice -> Dave