Minimum cost path in at most K steps

minimum_path_in_atmost_k_steps.py

class Solution(object):

    def solve(self, graph, steps, source, destination):
        min_cost = 9999999999999999
        min_path = None
        queue = [(source, 0, [source])]
        visited = {source: 0}

        while queue:
            current_city = queue[0]
            queue.pop(0)
            current_cost = current_city[1]
            current_path = current_city[2]

            if len(current_path) - 1 > steps:
                continue

            if current_city[0] == destination and current_cost < min_cost:
                min_cost = current_cost
                min_path = current_path

            neighbours = graph.get(current_city[0], [])

            for n in neighbours:
                if visited.get(n[0]) is None or visited[n[0]] > current_cost + n[1]:
                    queue.append((n[0], current_cost + n[1], current_path + [n[0]]))
                    visited[n[0]] = current_cost + n[1]

        return  min_path


if __name__ == "__main__":

    graph = {
        "A": [("B", 1), ("C", 5)],
        "B": [("C", 1)],
        "C": [("D", 1), ("E", 3)],
        "D": [("E", 1)]
    }

    max_steps = 3

    ans = Solution().solve(graph, max_steps, "A", "E")

    print(ans)