Сложность времени: самые дешевые рейсы в пределах K остановок

Question

Проблема:

Есть n городов, соединенных m рейсами. Каждый бой начинается с города и приходит к v с ценой w.

Теперь даны все города и рейсы вместе со стартовым городом src и пункт назначения dst, ваша задача найти самую дешевую цену от Src до DST с до K остановок. Если такого маршрута нет, выведите -1. ​​

Пример 1: Ввод: n = 3, ребра = [[0,1,100], [1,2,100], [0,2,500]] src = 0, dst = 2, k = 1 Выход: 200 Объяснение: Самая низкая цена от города 0 до города 2 с максимум 1 остановкой стоит 200.

Пример 2: Ввод: n = 3, ребра = [[0,1,100], [1,2,100], [0,2,500]] src = 0, dst = 2, k = 0 Вывод: 500 Объяснение: Самая низкая цена от города 0 до города 2 с не более 0 остановками стоит 500

Количество узлов n будет в диапазоне [1, 100], с узлами, помеченными от 0 до n - 1. Размер полетов будет в диапазоне [0, n * (n - 1) / 2]. Формат каждого рейса будет (src, dst, цена). Цена каждого рейса будет в диапазоне [1, 10000]. k находится в диапазоне [0, n - 1]. Дублированных рейсов или циклов самообслуживания не будет.

Я знаю, что есть стандартное решение Беллмана-Форда для этой проблемы. Но меня больше интересует временная сложность традиционного решения 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 больше случаев.