roads = { "S": [("A", 4), ("B", 1)], "A": [("G", 1)], "B": [("G", 2)] } estimate = {"S": 3, "A": 1, "B": 2, "G": 0} def search(use_cost): waiting = [(0, "S")] while waiting: cost, path = min(waiting, key=lambda item: estimate[item[1][-1]] + (item[0] if use_cost else 0)) waiting.remove((cost, path)) if path[-1] == "G": return path, cost for next_stop, price in roads[path[-1]]: waiting.append((cost + price, path + next_stop)) print(*search(False)) print(*search(True))