From 37e518cf9300cf88d71a2a63548be33fb0468cb4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Thu, 12 Nov 2020 17:21:00 +0100 Subject: report number of iterations --- algorithms.py | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'algorithms.py') diff --git a/algorithms.py b/algorithms.py index 0537607..bd3cb75 100644 --- a/algorithms.py +++ b/algorithms.py @@ -46,14 +46,16 @@ def find_shortest_path_dijkstra(nodes, source_id, target_id): # and walk_dist is the total length of the walk in meters queue = [(0, (source_id,))] visited = set() + iterations = 0 while queue: + iterations += 1 # consider an unchecked walk walk_dist, walk = heapq.heappop(queue) walk_end = walk[-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 @@ -77,12 +79,14 @@ def find_shortest_path_astar(nodes, source_id, target_id): """ Return the shortest path using A*. """ queue = [(0, (source_id,))] visited = set() + iterations = 0 while queue: walk_dist, walk = heapq.heappop(queue) + iterations += 1 walk_end = walk[-1] if walk_end == target_id: - return walk + return walk, iterations if walk_end in visited: continue visited.add(walk_end) -- cgit v1.2.1