diff options
Diffstat (limited to 'algorithms.py')
| -rw-r--r-- | algorithms.py | 15 |
1 files changed, 10 insertions, 5 deletions
diff --git a/algorithms.py b/algorithms.py index 1e70fa1..11f9e6b 100644 --- a/algorithms.py +++ b/algorithms.py @@ -69,24 +69,29 @@ 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 # 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 + # 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 = 0 - visited = set() + visited = {} while queue: # consider an unchecked walk walk_dist, walk = heapq.heappop(queue) - walk_end = walk[-1] iterations += 1 + walk_end = walk[-1] if walk_end == target_id: # you have reached your destination - return walk, iterations + return walk, iterations, visited if walk_end in visited: # there exists a shorter walk to walk_end continue # otherwise this is the shortest walk to walk_end - visited.add(walk_end) + if len(walk) == 1: + visited[walk_end] = (walk[-1], walk[-1], iterations) + else: + visited[walk_end] = (walk[-2], walk[-1], iterations) # consider all our neighbours for neighbour in nodes[walk_end].neighbours: if neighbour in visited: |