From 8b323af51c560e1951d1fd067fe11986732b79f0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Mon, 9 Nov 2020 17:52:57 +0100 Subject: update comment --- algorithms.py | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) (limited to 'algorithms.py') diff --git a/algorithms.py b/algorithms.py index 11f9e6b..707d55d 100644 --- a/algorithms.py +++ b/algorithms.py @@ -66,14 +66,20 @@ 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 contains multiple (walk_dist, (node_0, node_1, ... node_n))-tuples + """ Return the shortest path using Dijkstra's algorithm, as well as + the number of iterations it took.""" + # Queue contains multiple tuples of the form + # (walk_dist, ((node_0, iterations_0), ... (node_n, iterations_n))) # 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. - # iterations is the number of iterations the algorithm took before finding - # this node and is used for coloring. queue = [(0, (source_id,))] + + # Iterations is the number of iterations the algorithm took before finding + # a node and is used for coloring. iterations = 0 + + # For each node, visited contains the final edge of the shortest path to it + # and the number of iterations it took to get there. visited = {} while queue: -- cgit v1.2.1