count and store iterations in search algorithm

2 files changed, 4 insertions, 2 deletions

diff --git a/algorithms.py b/algorithms.py
index 8a6e2d3..1e70fa1 100644
--- a/algorithms.py
+++ b/algorithms.py
@@ -71,15 +71,17 @@ def find_shortest_path(nodes, source_id, target_id):
     # where (node_0, node_1, ... node_n) is a walk to node_n
     # and walk_dist is the total length of the walk in meters
     queue = [(0, (source_id,))]
+    iterations = 0
     visited = set()
 
     while queue:
         # consider an unchecked walk
         walk_dist, walk = heapq.heappop(queue)
         walk_end = walk[-1]
+        iterations += 1
         if walk_end == target_id:
             # you have reached your destination
-            return walk
+            return walk, iterations
         if walk_end in visited:
             # there exists a shorter walk to walk_end
             continue
diff --git a/server.py b/server.py
index f86cc60..d2bc8cc 100644
--- a/server.py
+++ b/server.py
@@ -29,7 +29,7 @@ def shortest_path(body):
     source_id = algorithms.get_closest_node_id(nodes, store.Node(-1, body['lat1'], body['lng1']))
     target_id = algorithms.get_closest_node_id(nodes, store.Node(-1, body['lat2'], body['lng2']))
 
-    path = algorithms.find_shortest_path(nodes, source_id, target_id)
+    path, iterations = algorithms.find_shortest_path(nodes, source_id, target_id)
     edges = []
     for i in range(len(path)-1):
         edges.append({"path": [[nodes[path[i]].lat, nodes[path[i]].lng],