Time complexity: Cheapst Flights within K stops

Question

Problem:

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

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.

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.

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

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.

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:

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 <= K+1:
                    result = min(result, currCost)
                elif stops <= K+1 and currCost < result:
                    for child, newCost in graph[node]:
                        newQ.append((child, currCost + newCost))
            q = newQ
            stops += 1
        return -1 if result == float('inf') else result

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?

user_10350247 · Answer

BFS usually runs on O(V + E) but that's because BFS algorithms usually have a visited array. In your case, instead of a visited array you simply check if your current path has more than K stops. So your algorithm will go to any of the N cities, K times. This makes is O(N^K).

For example, let's say you have 5 cities labeled 1-5 and you're going from city 1 to city 5, and K = 3. Worst case scenario, there were be bidirectional edges connecting every node. Your algorithm will start at city 1, then split to cities 2, 3, 4, and 5. Next, it'll go to city 2 and branch to 3, 4, 5, and also back to 1. Since there isn't a visited array, your code will unnecessarily check paths such as 1-2-1. Each case branches into N-1 more cases.

Time complexity: Cheapst Flights within K stops

1 Answers