diff options
Diffstat (limited to 'algorithms.py')
| -rw-r--r-- | algorithms.py | 14 |
1 files changed, 10 insertions, 4 deletions
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: |