问题:
有n个城市通过m次航班连接。每次航班从城市u开始并到达v,价格为w。
现在给出所有城市和航班,以及起始城市src和目的地dst,您的任务是找到从src到dst的最便宜价格,最多有k次停留。如果没有这样的路线,请输出-1。
示例1:
输入: n=3, edges=[[0,1,100],[1,2,100],[0,2,500]]、 src = 0、 dst = 2、 k = 1
输出: 200
解释:最多有一次中转,从城市0到城市2的最便宜价格为200。
示例2: 输入:n=3, edges=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=0 输出:500 解释:最多没有中转,从城市0到城市2的最便宜价格为500。 节点数n将在[1,100]范围内,节点标记为0至n-1。 航班的大小将在[0,n*(n-1)/2]范围内。 每次航班的格式将是(src,dst,price)。每个航班的价格将在[1,10000]范围内。 k在[0,n-1]的范围内。不会有任何重复的航班或自循环。 我知道这个问题有一个标准的贝尔曼-福德解决方案。但我更感兴趣的是传统BFS解决方案的时间复杂度,就像这里所示:
示例2: 输入:n=3, edges=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=0 输出:500 解释:最多没有中转,从城市0到城市2的最便宜价格为500。 节点数n将在[1,100]范围内,节点标记为0至n-1。 航班的大小将在[0,n*(n-1)/2]范围内。 每次航班的格式将是(src,dst,price)。每个航班的价格将在[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),我很困惑为什么会有指数级的时间复杂度?有人能说服我这里的时间复杂度是指数级的吗?