python - 时间复杂度 : 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.

我知道这个问题有一个标准的 Bellman-Ford 解决方案。但我对传统 BFS 解决方案的时间复杂度更感兴趣，如下所示:

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

我直觉上认为它的时间复杂度与 n 成线性关系，但许多人认为它是 O(n^k)，我很困惑为什么这个指数时间从何而来？有人能说服我这里的时间复杂度是指数级的吗？

Answer 1

BFS 通常在 O(V + E) 上运行，但这是因为 BFS 算法通常有一个已访问数组。在您的情况下，您只需检查当前路径是否有超过 K 个停靠点，而不是访问数组。因此，您的算法将前往 N 个城市中的任何一个，K 次。这使得是 O(N^K)。

例如，假设您有 5 个标记为 1-5 的城市，您要从城市 1 前往城市 5，并且 K = 3。最坏的情况是，每个节点都有双向边连接。您的算法将从城市 1 开始，然后拆分到城市 2、3、4 和 5。接下来，它会转到城市 2 并分支到 3、4、5，然后返回到 1。因为没有访问过的数组，您的代码将不必要地检查路径，例如 1-2-1。每个案例又分支成 N-1 个案例。