Cheapest Flights Within K Stops

Medium

Bellman-Ford capped at k+1 rounds

Problem

Find the cheapest price from src to dst using at most k stops.

In simple words

Relax edges at most k+1 times (Bellman-Ford style) so paths use at most k stops.

The idea

'At most k stops' means at most k+1 flights, which is Bellman-Ford stopped early: relax every flight for just k+1 rounds. Relax against the previous round's snapshot so a single round can't chain several flights together and exceed the stop limit.

←→stepspaceplay

dist[0, ∞, ∞, ∞]

1/9

Optimal

timeO(k*E)spaceO(V)

1dist[src] = 0, all others = ∞2repeat k+1 times:                 // at most k stops = k+1 edges3  for each flight (u → v, price): relax using the PREVIOUS round's dist4return dist[dst]   // -1 if still ∞

Input

nodes: 4, 5 edges

Memory

dist: [0, ∞, ∞, ∞]
round: —

Output

shortest dist: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n=4, flights=[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src=0, dst=3, k=1
Output:: 700
Explanation:: Best within 1 stop costs 700.

Example 2

Input:: n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1
Output:: 200
Explanation:: Two hops (200) beat the direct 500.

Example 3

Input:: n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=0
Output:: 500
Explanation:: With no stops, only the 500 flight works.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.