MediumGraphs · Bellman-Ford · Shortest Path

Cheapest Flights Within K Stops

flights[i] = [from, to, price] are one-way flights between airports 0…n−1. Return the cheapest price from src to dst using at most k stops in between, or -1.

n = 4, flights = [[0,1,200],[1,2,100],[1,3,300],[2,3,100]], src = 0, dst = 3, k = 1 → 500n = 3, flights = [[1,0,100],[1,2,200],[0,2,100]], src = 1, dst = 2, k = 1 → 200

Try:
CALL
1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Variables

The data structures the code is building

Airports and flights

The price under each airport is the cheapest found so far

Time and space complexity

E = number of flights. The highlighted row is the solution being traced.

Keyboard: ← → step, Space play or pause. Up to 7 airports and 14 flights, prices from 1 to 1000, no duplicate flights.