diff options
Diffstat (limited to 'algorithms.py')
| -rw-r--r-- | algorithms.py | 7 |
1 files changed, 7 insertions, 0 deletions
diff --git a/algorithms.py b/algorithms.py index 6e01287..d0988ee 100644 --- a/algorithms.py +++ b/algorithms.py @@ -1,5 +1,6 @@ import heapq import math +import time def length_haversine(p1, p2): @@ -22,12 +23,15 @@ def get_closest_node_id(nodes, source_node): min_node = None min_value = None + start = time.monotonic() + for node_id, node in nodes.items(): length = length_haversine(source_node, node) if min_node is None or length < min_value: min_node = node_id min_value = length + print(f"Found the closest node in {time.monotonic() - start} s") return min_node @@ -39,12 +43,15 @@ def find_shortest_path(nodes, source_id, target_id): queue = [(0, (source_id,))] visited = set() + start = time.monotonic() + while queue: # consider an unchecked walk walk_dist, walk = heapq.heappop(queue) walk_end = walk[-1] if walk_end == target_id: # you have reached your destination + print(f"Found a path in {time.monotonic() - start} s") return walk if walk_end in visited: # there exists a shorter walk to walk_end |