astar_path#

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

返回使用A*（”A星”）算法在源节点和目标节点之间的一条最短路径上的节点列表。

可能存在多条最短路径。此函数仅返回其中一条。

Parameters:
GNetworkX图
source节点

路径的起始节点

target节点

路径的终止节点

heuristic函数

用于评估从某个节点到目标节点的估计距离的函数。该函数接受两个节点参数并必须返回一个数值。 如果启发函数是不可接受的（即它可能高估从某个节点到达目标的成本），结果可能不是最短路径。 算法不支持更新同一节点的启发值，因为会缓存每个节点的首次启发计算结果。

weight字符串或函数

如果这是一个字符串，则将通过具有此键的边属性访问边权重（即，连接 u 到 v 的边的权重将是 G.edges[u, v][weight] ）。如果没有这样的边属性存在，则假定边的权重为1。 如果这是一个函数，边的权重是该函数返回的值。该函数必须接受三个位置参数：一条边的两个端点和该边的属性字典。该函数必须返回一个数值或None以表示隐藏边。

cutoff浮点数, 可选

如果提供了此参数，搜索将被限制在此值内。即，如果评估函数对节点n的值超过此值，该节点将不会被进一步扩展并被忽略。更正式地说，设h’(n)为启发函数，g(n)为从源节点到达n的成本。那么，如果g(n) + h’(n) > cutoff，该节点将不会被进一步探索。 注意，如果启发函数是不可接受的，即使路径满足截止条件，也可能被忽略。

Raises:
NetworkXNoPath

如果源节点和目标节点之间不存在路径。

See also

shortest_path, dijkstra_path

Notes

边权重属性必须是数值。 距离计算为遍历的加权边之和。

权重函数可以用于隐藏边，通过返回None。 例如 weight = lambda u, v, d: 1 if d['color']=="red" else None 将找到最短的红色路径。

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])  # 节点是二元组 (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)]
On this page