leetcode-graph

787. Cheapest Flights Within K Stops.py

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k):
        """
        Approach-Dijkstra's algorithm
        
        We can model this problem as graph problem and use shortest path algorithm to solve it.
        
        Problem formulation:
            Given a directed weighted graph with n nodes, find the shortest path between src (starting node) and dst (ending node) with up to pass k nodes.
        
        It's like variant of dijkstra's problem but there's one more constrains than classic dijkstra algorithm, should be within k stops. So, we don't care about if the cities is visited or not and all other distances becasue it might have shorter distance to a certain node but cannot have one more stops, which leads to incorrest anwer.
            We only need priority queue making sure we keep track of minimum path from src to dst.
            
        T: O(n + m log m), in worst case, we go through all cities and inster m edges into the prioity queue.
        S: O(n + m) for graph adjacency list            
        """
        w_g = collections.defaultdict(list)
        for a, b, p in flights:
            w_g[a].append((b, p))
        # priority queue
        heap = [(0, src, k)]
        while len(heap) != 0:
            # retrieve shortest path from starting node to that node takes O(1)
            cost, cur_node, n_stop  = heapq.heappop(heap)
            if cur_node == dst:
                # because we use pq to extend our potential flightpaths in increasing order of cost, we know once we've reached the destination dst that it was the lowest cost way to get there
                return cost
            if n_stop >= 0:
                for nei_node, p in w_g[cur_node]:
                    # using pq to contain current distance from startong node to nei_node is dn+w
                    heapq.heappush(heap, (cost + p, nei_node, n_stop-1))
        return -1
    
    def findCheapestPrice(self, n, flights, src, dst, k):
        """
        Approach- BFS
            1. We add city into the queue only if n_stops is less than k and current cost is less than min price
            2. Every time we encounter dst we compare the price and set it to the min because using bfs theire might be multiple path to reach the dst node.
        
        T: O(n + m), n is number of cities and m is number of flights
        S: O(n + m) for adjacency list.
        """
        w_g = collections.defaultdict(list)
        for a, b, p in flights:
            w_g[a].append((b, p))
        
        q = collections.deque([(0, src, k)])
        min_price = float("inf") # ans
        
        while len(q) != 0:
            cost, cur_city, n_stops = q.popleft()
            if cur_city == dst:
                min_price = min(min_price, cost)
            for nei_city, p in w_g[cur_city]:
                if cost <= min_price and n_stops >= 0:
                    q.append((cost + p, nei_city, n_stops - 1))
        return min_price if min_price != float("inf") else -1