Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Cheapest Flights Within K Stops

LeetCode #787Medium
Bellman-Ford bounded to K+1 hops

Given flights as directed weighted edges between cities, a source, a destination, and an integer k, return the cheapest total price to travel from source to destination using at most k intermediate stops, or -1 if no such route exists.

Asked atAmazonGoogle
step 1 / 15
weighted directed flights · src 0, dst 3, K=1
100100100500
0
1
2
3
cheapest cost from 0
nodecost
0∞
1∞
2∞
3∞
Bounded Bellman-Ford
▸
1dist = [∞...]; dist[src] = 0
2repeat K+1 times:
3    prev = copy(dist)        // freeze last round
4    for each (u → v, w):
5        if prev[u] + w < dist[v]:
6            dist[v] = prev[u] + w
7    // each round adds at most one hop
8return dist[dst] (or −1 if ∞)
state
  • src0
  • dst3
  • K stops1
  • max hops2

line 1Find the cheapest fare from city 0 to city 3 using AT MOST K=1 stop — meaning at most K+1 = 2 flights (hops). Cheapest total ignoring the limit is 0→1→2→3 = 300, but that uses 2 stops. Only routes with ≤ 1 stop are legal, so we cannot just run plain Dijkstra; we must bound the number of hops.