minor refactor

1 files changed, 19 insertions, 10 deletions

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