Cheapest Flights Within K Stops — Bellman-Ford / BFS

Problem

Find the cheapest price from src to dst with at most k stops (k+1 edges), or -1 if no such route.

Approach — Bellman-Ford (k+1 iterations)

Relax all edges k+1 times. Use a copy of dist array each iteration to not use same-round updates.

Time: O(k*E) | Space: O(V)

Solutions

Python — Bellman-Ford

class Solution:
    def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
        dist=[float('inf')]*n; dist[src]=0
        for _ in range(k+1):
            tmp=dist[:]
            for u,v,w in flights:
                if dist[u]!=float('inf') and dist[u]+w<tmp[v]:
                    tmp[v]=dist[u]+w
            dist=tmp
        return dist[dst] if dist[dst]!=float('inf') else -1

Python — BFS (level = stop count)

from collections import defaultdict, deque
class Solution:
    def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
        adj=defaultdict(list)
        for u,v,w in flights: adj[u].append((v,w))
        dist=[float('inf')]*n; dist[src]=0
        q=deque([(src,0)]); stops=0
        while q and stops<=k:
            for _ in range(len(q)):
                u,cost=q.popleft()
                for v,w in adj[u]:
                    if cost+w<dist[v]:
                        dist[v]=cost+w; q.append((v,dist[v]))
            stops+=1
        return dist[dst] if dist[dst]!=float('inf') else -1

Complexity

Bellman-Ford: O(k*E) | Space: O(V)