diff options
| -rw-r--r-- | algorithms.py | 11 |
1 files changed, 7 insertions, 4 deletions
diff --git a/algorithms.py b/algorithms.py index bd3cb75..c385991 100644 --- a/algorithms.py +++ b/algorithms.py @@ -77,13 +77,13 @@ def find_shortest_path_dijkstra(nodes, source_id, target_id): def find_shortest_path_astar(nodes, source_id, target_id): """ Return the shortest path using A*. """ - queue = [(0, (source_id,))] + queue = [(0, 0, (source_id,))] visited = set() iterations = 0 while queue: - walk_dist, walk = heapq.heappop(queue) iterations += 1 + _, walk_dist, walk = heapq.heappop(queue) walk_end = walk[-1] if walk_end == target_id: return walk, iterations @@ -94,7 +94,10 @@ def find_shortest_path_astar(nodes, source_id, target_id): if neighbour in visited: continue # simple heuristic - new_dist = walk_dist + length_haversine(nodes[walk_end], neighbour) + length_haversine(neighbour, nodes[target_id]) + new_dist = walk_dist + length_haversine(nodes[walk_end], neighbour) new_walk = walk + (neighbour.id,) - heapq.heappush(queue, (new_dist, new_walk)) + heapq.heappush(queue, (new_dist + length_haversine(nodes[neighbour.id], + nodes[target_id]), + new_dist, + new_walk)) return None |