787. Cheapest Flights Within K Stops - cocoder39/coco39_LC GitHub Wiki

Option 1: Dijkstra Unlike traditional Dijkstra where cost is the only factor being considered when deciding priority, we should also allow a node to be added to queue if it can reduce #stop (even thought it may cost more than if we take another route which also passes through this node).

Time complexity: T = O(E * log E)

• O(E) to build graph
• we perform heap push for each edge O(E * log E)

Space complexity: O(E + V) to build graph and O(E) for queue

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for f, t, p in flights:
            graph[f].append((t, p))
        
        heap = [(0, -1, src)] 
        cost = [float("inf")] * n
        steps = [float("inf")] * n
        while heap:
            totalPrice, stopCount, curNode = heapq.heappop(heap)
            
            if stopCount <= k and curNode == dst:
                    return totalPrice
                
            if stopCount >= k:
                continue
                
            cost[curNode] = totalPrice
            steps[curNode] = stopCount
                
            for neighbor, price in graph[curNode]:
                if cost[neighbor] > totalPrice + price:
                    cost[neighbor] = totalPrice + price
                    heapq.heappush(heap, (totalPrice+price, stopCount+1, neighbor))
                elif steps[neighbor] > stopCount + 1:
                    steps[neighbor] = stopCount + 1
                    heapq.heappush(heap, (totalPrice+price, stopCount+1, neighbor))
                    
        return -1

Option 2: recursion + memo

Time complexity: O(V * k) as there are V * k states in memo space complexity: O(V + E) for graph building, O (V * K) for memo, O(V * K) for recursion stack since recursion stack is not deeper than total state count V*k

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for f, t, p in flights:
            graph[f].append((t, p))
        
        def helper(node, stop):
            if node in memo and stop in memo[node]:
                return memo[node][stop]
            
            if node == dst:
                return 0
            
            if stop < 0:
                return float("inf")
            
            res = float("inf")
            for nextNode, cost in graph[node]:
                res = min(res, cost + helper(nextNode, stop-1))
            memo[node][stop] = res
            return res
        
        memo = collections.defaultdict(dict)
        helper(src, k)
        return memo[src][k] if memo[src][k] != float("inf") else -1

Option 3: bfs

performing k levels of bfs, meanwhile updating the distance for each node within the search.

Time complexity: k times while loop, each loop iterates M edges and M < E so O(E * k) is an upper bound

space complexity: O(E + V) to build graph, O(V*K) to build distances dict. The size of queue is hard to determine, a node may be at same level of different paths so len(queue) can be greater than V. O(E * K) is a good upper bound considering executing while loop K times and each time won't iterate all E edges (each time iterate edges for nodes at stops level)

class Solution:
    
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        
        graph = collections.defaultdict(list)
        for f, t, p in flights:
            graph[f].append((t, p))
            
        distances = {(src, 0): 0}
        queue = deque([src])
        stops = 0
        ans = float("inf")
        
        while queue and stops < K + 1:
            
            for _ in range(len(queue)):
                curNode = queue.popleft()
                for nextNode, cost in graph[curNode]:
                    if stops == K and nextNode != dst:
                        continue
                        
                    dU = distances.get((curNode, stops), float("inf"))
                    dV = distances.get((nextNode, stops + 1), float("inf"))
                    if dU + cost < dV:
                        distances[nextNode, stops + 1] = dU + cost
                        queue.append(nextNode)
                            
                        if nextNode == dst:
                            ans = min(ans, dU + cost)
            stops += 1   
        
        return -1 if ans == float("inf") else ans

Option 4: bellman-ford

original bellman-ford 对所有的边进行n-1轮松弛操作，因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1边. To get shortest path with k+2 nodes we need to iterate k+1 times

Time complexity is O(EK) and space is O(V)

attention: temp[t] = min(temp[t], distances[f] + p) instead of distances[t] = min(distances[t], distances[f] + p) or temp[t] = min(temp[t], temp[f] + p)

class Solution:
    
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        distances = [float('inf')] * n
        distances[src] = 0
        
        for i in range(min(K+1, n-1)):
            temp = distances[:]
            for f, t, p in flights:
                temp[t] = min(temp[t], distances[f] + p)
            distances = temp[:]
                    
        return -1 if distances[dst] == float("inf") else distances[dst]