diff options
| author | Gustav Sörnäs <gusso230@student.liu.se> | 2020-11-12 17:21:09 +0100 |
|---|---|---|
| committer | Gustav Sörnäs <gusso230@student.liu.se> | 2020-11-20 13:39:57 +0100 |
| commit | 41c98fcda3e5b440906d5e148cae41b8951ab40b (patch) | |
| tree | 13cee6802f476c5f5cc8f4aaf0207a7fb65c4d9e | |
| parent | 37e518cf9300cf88d71a2a63548be33fb0468cb4 (diff) | |
| download | tdde25-a-star.tar.gz | |
correct A*a-star
| -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 |