Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Shortest paths and path lengths using the A* ("A star") algorithm."""
3from heapq import heappop, heappush
4from itertools import count
6import networkx as nx
7from networkx.algorithms.shortest_paths.weighted import _weight_function
9__all__ = ["astar_path", "astar_path_length"]
12@nx._dispatchable(edge_attrs="weight", preserve_node_attrs="heuristic")
13def astar_path(G, source, target, heuristic=None, weight="weight", *, cutoff=None):
14 """Returns a list of nodes in a shortest path between source and target
15 using the A* ("A-star") algorithm.
17 There may be more than one shortest path. This returns only one.
19 Parameters
20 ----------
21 G : NetworkX graph
23 source : node
24 Starting node for path
26 target : node
27 Ending node for path
29 heuristic : function
30 A function to evaluate the estimate of the distance
31 from the a node to the target. The function takes
32 two nodes arguments and must return a number.
33 If the heuristic is inadmissible (if it might
34 overestimate the cost of reaching the goal from a node),
35 the result may not be a shortest path.
36 The algorithm does not support updating heuristic
37 values for the same node due to caching the first
38 heuristic calculation per node.
40 weight : string or function
41 If this is a string, then edge weights will be accessed via the
42 edge attribute with this key (that is, the weight of the edge
43 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
44 such edge attribute exists, the weight of the edge is assumed to
45 be one.
46 If this is a function, the weight of an edge is the value
47 returned by the function. The function must accept exactly three
48 positional arguments: the two endpoints of an edge and the
49 dictionary of edge attributes for that edge. The function must
50 return a number or None to indicate a hidden edge.
52 cutoff : float, optional
53 If this is provided, the search will be bounded to this value. I.e. if
54 the evaluation function surpasses this value for a node n, the node will not
55 be expanded further and will be ignored. More formally, let h'(n) be the
56 heuristic function, and g(n) be the cost of reaching n from the source node. Then,
57 if g(n) + h'(n) > cutoff, the node will not be explored further.
58 Note that if the heuristic is inadmissible, it is possible that paths
59 are ignored even though they satisfy the cutoff.
61 Raises
62 ------
63 NetworkXNoPath
64 If no path exists between source and target.
66 Examples
67 --------
68 >>> G = nx.path_graph(5)
69 >>> print(nx.astar_path(G, 0, 4))
70 [0, 1, 2, 3, 4]
71 >>> G = nx.grid_graph(dim=[3, 3]) # nodes are two-tuples (x,y)
72 >>> nx.set_edge_attributes(G, {e: e[1][0] * 2 for e in G.edges()}, "cost")
73 >>> def dist(a, b):
74 ... (x1, y1) = a
75 ... (x2, y2) = b
76 ... return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
77 >>> print(nx.astar_path(G, (0, 0), (2, 2), heuristic=dist, weight="cost"))
78 [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
80 Notes
81 -----
82 Edge weight attributes must be numerical.
83 Distances are calculated as sums of weighted edges traversed.
85 The weight function can be used to hide edges by returning None.
86 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
87 will find the shortest red path.
89 See Also
90 --------
91 shortest_path, dijkstra_path
93 """
94 if source not in G:
95 raise nx.NodeNotFound(f"Source {source} is not in G")
97 if target not in G:
98 raise nx.NodeNotFound(f"Target {target} is not in G")
100 if heuristic is None:
101 # The default heuristic is h=0 - same as Dijkstra's algorithm
102 def heuristic(u, v):
103 return 0
105 weight = _weight_function(G, weight)
107 G_succ = G._adj # For speed-up (and works for both directed and undirected graphs)
109 # The queue stores priority, node, cost to reach, and parent.
110 # Uses Python heapq to keep in priority order.
111 # Add a counter to the queue to prevent the underlying heap from
112 # attempting to compare the nodes themselves. The hash breaks ties in the
113 # priority and is guaranteed unique for all nodes in the graph.
114 c = count()
115 queue = [(0, next(c), source, 0, None)]
117 # Maps enqueued nodes to distance of discovered paths and the
118 # computed heuristics to target. We avoid computing the heuristics
119 # more than once and inserting the node into the queue too many times.
120 enqueued = {}
121 # Maps explored nodes to parent closest to the source.
122 explored = {}
124 while queue:
125 # Pop the smallest item from queue.
126 _, __, curnode, dist, parent = heappop(queue)
128 if curnode == target:
129 path = [curnode]
130 node = parent
131 while node is not None:
132 path.append(node)
133 node = explored[node]
134 path.reverse()
135 return path
137 if curnode in explored:
138 # Do not override the parent of starting node
139 if explored[curnode] is None:
140 continue
142 # Skip bad paths that were enqueued before finding a better one
143 qcost, h = enqueued[curnode]
144 if qcost < dist:
145 continue
147 explored[curnode] = parent
149 for neighbor, w in G_succ[curnode].items():
150 cost = weight(curnode, neighbor, w)
151 if cost is None:
152 continue
153 ncost = dist + cost
154 if neighbor in enqueued:
155 qcost, h = enqueued[neighbor]
156 # if qcost <= ncost, a less costly path from the
157 # neighbor to the source was already determined.
158 # Therefore, we won't attempt to push this neighbor
159 # to the queue
160 if qcost <= ncost:
161 continue
162 else:
163 h = heuristic(neighbor, target)
165 if cutoff and ncost + h > cutoff:
166 continue
168 enqueued[neighbor] = ncost, h
169 heappush(queue, (ncost + h, next(c), neighbor, ncost, curnode))
171 raise nx.NetworkXNoPath(f"Node {target} not reachable from {source}")
174@nx._dispatchable(edge_attrs="weight", preserve_node_attrs="heuristic")
175def astar_path_length(
176 G, source, target, heuristic=None, weight="weight", *, cutoff=None
177):
178 """Returns the length of the shortest path between source and target using
179 the A* ("A-star") algorithm.
181 Parameters
182 ----------
183 G : NetworkX graph
185 source : node
186 Starting node for path
188 target : node
189 Ending node for path
191 heuristic : function
192 A function to evaluate the estimate of the distance
193 from the a node to the target. The function takes
194 two nodes arguments and must return a number.
195 If the heuristic is inadmissible (if it might
196 overestimate the cost of reaching the goal from a node),
197 the result may not be a shortest path.
198 The algorithm does not support updating heuristic
199 values for the same node due to caching the first
200 heuristic calculation per node.
202 weight : string or function
203 If this is a string, then edge weights will be accessed via the
204 edge attribute with this key (that is, the weight of the edge
205 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
206 such edge attribute exists, the weight of the edge is assumed to
207 be one.
208 If this is a function, the weight of an edge is the value
209 returned by the function. The function must accept exactly three
210 positional arguments: the two endpoints of an edge and the
211 dictionary of edge attributes for that edge. The function must
212 return a number or None to indicate a hidden edge.
214 cutoff : float, optional
215 If this is provided, the search will be bounded to this value. I.e. if
216 the evaluation function surpasses this value for a node n, the node will not
217 be expanded further and will be ignored. More formally, let h'(n) be the
218 heuristic function, and g(n) be the cost of reaching n from the source node. Then,
219 if g(n) + h'(n) > cutoff, the node will not be explored further.
220 Note that if the heuristic is inadmissible, it is possible that paths
221 are ignored even though they satisfy the cutoff.
223 Raises
224 ------
225 NetworkXNoPath
226 If no path exists between source and target.
228 See Also
229 --------
230 astar_path
232 """
233 if source not in G or target not in G:
234 msg = f"Either source {source} or target {target} is not in G"
235 raise nx.NodeNotFound(msg)
237 weight = _weight_function(G, weight)
238 path = astar_path(G, source, target, heuristic, weight, cutoff=cutoff)
239 return sum(weight(u, v, G[u][v]) for u, v in zip(path[:-1], path[1:]))