From a178b3088fa8e90a080926c79d608497e4b56448 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Thu, 12 Nov 2020 14:14:27 +0100 Subject: count and store iterations in search algorithm --- algorithms.py | 4 +++- server.py | 2 +- 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], -- cgit v1.2.1