title: Time complexity: Cheapst Flights within K stops
body: <blockquote>
    <p>Problem:</p>
    
    <p>There are n cities connected by m flights. Each fight starts from city
    u and arrives at v with a price w.</p>
    
    <p>Now given all the cities and flights, together with starting city src
    and the destination dst, your task is to find the cheapest price from
    src to dst with up to k stops. If there is no such route, output -1.</p>
    
    <p>Example 1: Input:  n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src
    = 0, dst = 2, k = 1 Output: 200 Explanation:  The cheapest price from city 0 to city 2 with at most 1 stop costs 200.</p>
    
    <p>Example 2: Input:  n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src
    = 0, dst = 2, k = 0 Output: 500 Explanation:  The cheapest price from city 0 to city 2 with at most 0 stop costs 500</p>
    
    <p>The number of nodes n will be in range [1, 100], with nodes labeled
    from 0 to n - 1.
    The size of flights will be in range [0, n * (n - 1)
    / 2]. 
    The format of each flight will be (src, dst, price). The price
    of each flight will be in the range [1, 10000]. 
    k is in the range of [0, n - 1]. 
    There will not be any duplicated flights or self cycles.</p>
  </blockquote>
  
  <p>I know there's a standard Bellman-Ford solution to this problem. But I'm more interested in the time complexity of a traditional BFS solution, as shown here:</p>
  
  <pre><code>import collections
  
  class Solution:
      def findCheapestPrice(self, n, flights, src, dst, K):
          """
          :type n: int
          :type flights: List[List[int]]
          :type src: int
          :type dst: int
          :type K: int
          :rtype: int
  
          BFS
  
          """           
          graph = collections.defaultdict(list)
          for parent, child, value in flights:
              graph[parent].append((child, value))
  
          q = [(src, 0)]
          stops = 0
          result = float('inf')
          while q:
              newQ = []
              for node, currCost in q:
                  if node == dst and stops &lt;= K+1:
                      result = min(result, currCost)
                  elif stops &lt;= K+1 and currCost &lt; result:
                      for child, newCost in graph[node]:
                          newQ.append((child, currCost + newCost))
              q = newQ
              stops += 1
          return -1 if result == float('inf') else result
  </code></pre>
  
  <p>I intuitively think the time complexity of this is linear to n, but many think it's O(n^k), I'm confused as why where this exponential time is coming from? Can someone convince me time complexity here is exponential?</p>