astar_path#

astar_path(G, source, target, heuristic=None, weight='weight', *, cutoff=None)[source]#

Returns a list of nodes in a shortest path between source and target using the A* (“A-star”) algorithm.

There may be more than one shortest path. This returns only one.

Parameters:

GNetworkX graph
sourcenode: Starting node for path
targetnode: Ending node for path
heuristicfunction: A function to evaluate the estimate of the distance from the a node to the target. The function takes two nodes arguments and must return a number. If the heuristic is inadmissible (if it might overestimate the cost of reaching the goal from a node), the result may not be a shortest path. The algorithm does not support updating heuristic values for the same node due to caching the first heuristic calculation per node.
weightstring or function: If this is a string, then edge weights will be accessed via the edge attribute with this key (that is, the weight of the edge joining u to v will be G.edges[u, v][weight]). If no such edge attribute exists, the weight of the edge is assumed to be one. If this is a function, the weight of an edge is the value returned by the function. The function must accept exactly three positional arguments: the two endpoints of an edge and the dictionary of edge attributes for that edge. The function must return a number or None to indicate a hidden edge.
cutofffloat, optional: If this is provided, the search will be bounded to this value. I.e. if the evaluation function surpasses this value for a node n, the node will not be expanded further and will be ignored. More formally, let h’(n) be the heuristic function, and g(n) be the cost of reaching n from the source node. Then, if g(n) + h’(n) > cutoff, the node will not be explored further. Note that if the heuristic is inadmissible, it is possible that paths are ignored even though they satisfy the cutoff.

Raises:

NetworkXNoPath: If no path exists between source and target.

See also

shortest_path, dijkstra_path

Notes

Edge weight attributes must be numerical. Distances are calculated as sums of weighted edges traversed.

The weight function can be used to hide edges by returning None. So weight = lambda u, v, d: 1 if d['color']=="red" else None will find the shortest red path.

Examples

>>> G = nx.path_graph(5)
>>> print(nx.astar_path(G, 0, 4))
[0, 1, 2, 3, 4]
>>> G = nx.grid_graph(dim=[3, 3])  # nodes are two-tuples (x,y)
>>> nx.set_edge_attributes(G, {e: e[1][0] * 2 for e in G.edges()}, "cost")
>>> def dist(a, b):
...     (x1, y1) = a
...     (x2, y2) = b
...     return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
>>> print(nx.astar_path(G, (0, 0), (2, 2), heuristic=dist, weight="cost"))
[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]