A map is a dict from each place to (neighbour, cost) pairs, with no negative costs. Find the cheapest route between two places and the route itself.

g = {"a": [("b", 7), ("c", 1)],
     "c": [("b", 2)], "b": []}
cheapest_route(g, "a", "b")
# (3, ["a", "c", "b"])

Keep a priority queue of places to visit, ordered by cost so far. The cheapest entry you pop can never be improved, because every other route costs at least as much and costs are not negative.

import heapq

heap = [(0, "a")]
cost, node = heapq.heappop(heap)
heapq.heappush(heap, (cost + 7, "b"))

A place can sit in the heap several times with different costs. When you pop an entry worse than the best known cost, skip it. To rebuild the route, remember each place's predecessor.

Write cheapest_route(graph, start, goal) returning (total_cost, path), where path is the list of places from start to goal, or None if goal cannot be reached. Use heapq. A place may appear only as a neighbour, without a key of its own.

The explanation opens here once every check passes.