| # -*- coding: utf-8 -*- |
| """Shortest paths and path lengths using A* ("A star") algorithm. |
| """ |
| |
| # Copyright (C) 2004-2011 by |
| # Aric Hagberg <hagberg@lanl.gov> |
| # Dan Schult <dschult@colgate.edu> |
| # Pieter Swart <swart@lanl.gov> |
| # All rights reserved. |
| # BSD license. |
| |
| from heapq import heappush, heappop |
| from networkx import NetworkXError |
| import networkx as nx |
| |
| __author__ = "\n".join(["Salim Fadhley <salimfadhley@gmail.com>", |
| "Matteo Dell'Amico <matteodellamico@gmail.com>"]) |
| __all__ = ['astar_path', 'astar_path_length'] |
| |
| |
| def astar_path(G, source, target, heuristic=None, weight='weight'): |
| """Return 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 |
| ---------- |
| G : NetworkX graph |
| |
| source : node |
| Starting node for path |
| |
| target : node |
| Ending node for path |
| |
| heuristic : function |
| 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. |
| |
| weight: string, optional (default='weight') |
| Edge data key corresponding to the edge weight. |
| |
| Raises |
| ------ |
| NetworkXNoPath |
| If no path exists between source and target. |
| |
| 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) |
| >>> 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),dist)) |
| [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)] |
| |
| |
| See Also |
| -------- |
| shortest_path, dijkstra_path |
| |
| """ |
| if G.is_multigraph(): |
| raise NetworkXError("astar_path() not implemented for Multi(Di)Graphs") |
| |
| if heuristic is None: |
| # The default heuristic is h=0 - same as Dijkstra's algorithm |
| def heuristic(u, v): |
| return 0 |
| # The queue stores priority, node, cost to reach, and parent. |
| # Uses Python heapq to keep in priority order. |
| # Add each node's hash to the queue to prevent the underlying heap from |
| # attempting to compare the nodes themselves. The hash breaks ties in the |
| # priority and is guarenteed unique for all nodes in the graph. |
| queue = [(0, hash(source), source, 0, None)] |
| |
| # Maps enqueued nodes to distance of discovered paths and the |
| # computed heuristics to target. We avoid computing the heuristics |
| # more than once and inserting the node into the queue too many times. |
| enqueued = {} |
| # Maps explored nodes to parent closest to the source. |
| explored = {} |
| |
| while queue: |
| # Pop the smallest item from queue. |
| _, __, curnode, dist, parent = heappop(queue) |
| |
| if curnode == target: |
| path = [curnode] |
| node = parent |
| while node is not None: |
| path.append(node) |
| node = explored[node] |
| path.reverse() |
| return path |
| |
| if curnode in explored: |
| continue |
| |
| explored[curnode] = parent |
| |
| for neighbor, w in G[curnode].items(): |
| if neighbor in explored: |
| continue |
| ncost = dist + w.get(weight, 1) |
| if neighbor in enqueued: |
| qcost, h = enqueued[neighbor] |
| # if qcost < ncost, a longer path to neighbor remains |
| # enqueued. Removing it would need to filter the whole |
| # queue, it's better just to leave it there and ignore |
| # it when we visit the node a second time. |
| if qcost <= ncost: |
| continue |
| else: |
| h = heuristic(neighbor, target) |
| enqueued[neighbor] = ncost, h |
| heappush(queue, (ncost + h, hash(neighbor), neighbor, |
| ncost, curnode)) |
| |
| raise nx.NetworkXNoPath("Node %s not reachable from %s" % (source, target)) |
| |
| |
| def astar_path_length(G, source, target, heuristic=None, weight='weight'): |
| """Return the length of the shortest path between source and target using |
| the A* ("A-star") algorithm. |
| |
| Parameters |
| ---------- |
| G : NetworkX graph |
| |
| source : node |
| Starting node for path |
| |
| target : node |
| Ending node for path |
| |
| heuristic : function |
| 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. |
| |
| Raises |
| ------ |
| NetworkXNoPath |
| If no path exists between source and target. |
| |
| See Also |
| -------- |
| astar_path |
| |
| """ |
| path = astar_path(G, source, target, heuristic, weight) |
| return sum(G[u][v].get(weight, 1) for u, v in zip(path[:-1], path[1:])) |