1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
# -*- coding: utf-8 -*-
"""
Shortest paths and path lengths using A* ("A star") algorithm.
"""
__author__ =\
"""Salim Fadhley <salimfadhley@gmail.com>
Matteo Dell'Amico <matteodellamico@gmail.com>"""
# Copyright (C) 2004-2008 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
__all__ = ['astar_path','astar_path_length']
def astar_path(G, source, target, heuristic=None):
"""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.
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((x1, y1), (x2, y2)):
... 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.
queue = [(0, 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].iteritems():
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, neighbor, ncost, curnode))
raise NetworkXError("Node %s not reachable from %s"%(source,target))
def astar_path_length(G, source, target, heuristic=None):
"""Return a list of nodes in a 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.
See Also
--------
astar_path()
"""
# FIXME: warn if G.weighted==False
path=astar_path(G,source,target,heuristic)
return sum(G[u][v].get('weight',1) for u,v in zip(path[:-1],path[1:]))
|
