Core Insight Improve a node’s known cost only when a newly discovered path is genuinely better.
Common Pitfall Discard stale priority-queue entries instead of expanding them a second time.
Description
Find cheapest flight path with at most k stops (Bellman-Ford).
Constraints
- Time Complexity:
O(K·E) - Space Complexity:
O(V)
Tags
dynamic-programmingdfsbfsgraphheapshortest-path
Implementation Plan Translate the invariant into these small, testable moves.
- Initialize distances and a frontier.
- Take the cheapest candidate.
- Relax each outgoing edge.
- Repeat until the target or all reachable nodes are settled.
def findCheapestPrice(n, flights, src, dst, k):
prices = [float("inf")] * n
prices[src] = 0
for i in range(k + 1):
tmpPrices = prices.copy()
for s, d, p in flights:
if prices[s] == float("inf"):
continue
if prices[s] + p < tmpPrices[d]:
tmpPrices[d] = prices[s] + p
prices = tmpPrices
return -1 if prices[dst] == float("inf") else prices[dst]