Python: Shortest path from dictionary that contains list of lists(name,weight)

Question

I have an adjacency list that looks like the following where each key contains a list of lists:

{'a': [['b', 5], ['c', 2]], 'b': [['e', 1], ['d', 7]], 'c': [['d', 7]], 'e': [['f', 2]], 'd': [['f', 2]], 'f': ['treasure']}

I'm trying to iterate starting from point A to any given key that will have treasure in it (in this case it is only F). However I am trying to find the shortest overall path and I'm not quite sure how to do this using a dictionary. Thank you in advanced for your help!

I've used BFS to construct the adjacency list you see above however I can't quite find the proper information on how to go about iterating over it to find a shortest path/all paths.

Answer 1

You should use the Dijkstra's algorithm, it is the best one for shortest paths between nodes in a graph like road networks.

For example:

import heapq

def shortest_path(graph, start):
    heap = [(0, start)]
    distances = {start: 0}
    path = {start: []}
    while heap:
        (cost, current) = heapq.heappop(heap)
        if 'treasure' in graph[current]:
            return path[current] + [current]
        for neighbor, weight in graph[current]:
            if neighbor == 'treasure':
                return path[current] + [current, neighbor]
            old_cost = distances.get(neighbor, float('inf'))
            new_cost = cost + weight
            if new_cost < old_cost:
                distances[neighbor] = new_cost
                heapq.heappush(heap, (new_cost, neighbor))
                path[neighbor] = path[current] + [current]
    return None

graph = {'a': [['b', 5], ['c', 2]], 'b': [['e', 1], ['d', 7]], 'c': [['d', 7]], 'e': [['f', 2]], 'd': [['f', 2]], 'f': ['treasure']}
print(shortest_path(graph, 'a'))  # Output: ['a', 'c', 'd', 'f', 'treasure']