From d2791410cc886ef9f1fbed7b9525477963b8b994 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Fri, 6 Nov 2020 10:46:13 +0100 Subject: minor refactor --- algorithms.py | 29 +++++++++++++++++++---------- 1 file changed, 19 insertions(+), 10 deletions(-) (limited to 'algorithms.py') diff --git a/algorithms.py b/algorithms.py index 3c84cf2..9d83b26 100644 --- a/algorithms.py +++ b/algorithms.py @@ -33,23 +33,32 @@ def get_closest_node_id(nodes, source_node): def find_shortest_path(nodes, source_id, target_id): """ Return the shortest path using Dijkstra's algortihm. """ - queue = [] + # queue contains multiple (path_length, (node_0, node_1, ... node_n))-tuples + # where (node_0, node_1, ... node_n) is a walk to node_n + queue = [(0, (source_id,))] visited = set() - print("neighbours", nodes[source_id].neighbours) - for neighbour in nodes[source_id].neighbours: - heapq.heappush(queue, (length_haversine(nodes[source_id], neighbour), (source_id, neighbour.id))) - while queue: - cand_dist, cand_path = heapq.heappop(queue) - walk_end = cand_path[-1] + # consider an unchecked walk + walk_dist, walk = heapq.heappop(queue) + walk_end = walk[-1] if walk_end == target_id: - return cand_path + # you have reached your destination + return walk if walk_end in visited: + # there exists a shorter walk to walk_end continue + # otherwise this is the shortest walk to walk_end visited.add(walk_end) + # consider all our neighbours for neighbour in nodes[walk_end].neighbours: - if neighbour not in visited: - heapq.heappush(queue, (cand_dist + length_haversine(nodes[walk_end], neighbour), cand_path + (neighbour.id, ))) + if neighbour in visited: + # there exists a shorter walk to neighbour + continue + # otherwise this MIGHT be the shortest walk to neighbour + # so put it in the queue + new_dist = walk_dist + length_haversine(nodes[walk_end], neighbour) + new_walk = walk + (neighbour.id,) + heapq.heappush(queue, (new_dist, new_walk)) # no path found return None -- cgit v1.2.1