Warning: This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#787) before relying on it.

Cheapest Flights Within K Stops

An interactive visualization of the modified Bellman-Ford algorithm. Watch how edge relaxation across K+1 rounds finds the cheapest flight route with at most K intermediate stops.

Shortest Path LeetCode 787 ↗ Medium

The Problem

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from, to, price] indicates there is a flight from city from to city to with cost price.

You are also given three integers src, dst, and k. Return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Interactive Visualization

Nodes (n)

Edges (from,to,price; ...)

Source

Destination

K (max stops)

Preset

Speed:

Flight Network

Code

fun findCheapestPrice(n: Int, flights: Array<IntArray>, src: Int, dst: Int, k: Int): Int {    var prices = IntArray(n) { Int.MAX_VALUE }    prices[src] = 0    for (i in 0..k) {        val tmp = prices.copyOf()        for ((u, v, w) in flights.map { Triple(it[0], it[1], it[2]) }) {            if (prices[u] == Int.MAX_VALUE)                continue            if (prices[u] + w < tmp[v])                tmp[v] = prices[u] + w        }        prices = tmp    }    return if (prices[dst] != Int.MAX_VALUE) prices[dst] else -1

def findCheapestPrice(n, flights, src, dst, k):    prices = [float('inf')] * n    prices[src] = 0    for i in range(k + 1):        tmp = prices.copy()        for u, v, w in flights:            if prices[u] == float('inf'):                continue            if prices[u] + w < tmp[v]:                tmp[v] = prices[u] + w        prices = tmp    return prices[dst] if prices[dst] != float('inf') else -1

Status

Press Step or Play to begin.

How It Works

Key Insight

This is a modified Bellman-Ford algorithm. Standard Bellman-Ford runs V-1 rounds of edge relaxation to find shortest paths. Here, we limit to K+1 rounds because K stops means at most K+1 edges (flights) in the path. Crucially, we use a copy of the prices array each round so that updates within one round do not cascade — ensuring we only use paths with at most one more edge per round.

The Algorithm

Initialize: set prices[src] = 0, all others to infinity
K+1 rounds: each round allows one more flight (edge) in the path
Each round: copy prices to tmp, then try relaxing every edge (u, v, w)
Relax: if prices[u] + w < tmp[v], update tmp[v] = prices[u] + w
Key detail: we read from prices (previous round) but write to tmp (current round) — this prevents using more edges than allowed
Result: after K+1 rounds, prices[dst] is the cheapest price, or -1 if unreachable

Complexity

Time O(K * E)

Space O(V)

We run K+1 rounds, each iterating over all E edges. We store two arrays of size V (the current prices and the temporary copy).