From 41c98fcda3e5b440906d5e148cae41b8951ab40b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Thu, 12 Nov 2020 17:21:09 +0100 Subject: correct A* --- algorithms.py | 11 +++++++---- 1 file 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 -- cgit v1.2.1