Stage 4: Advanced Techniques·Advanced Graph

Medium#7879 min readGraphBellman-FordDijkstraLeetCode

Cheapest Flights Within K Stops

Modified Dijkstra with stop counter

Bellman-Ford with K rounds. You already know this from your arb bot.

Published Apr 16, 2026

Problem

You're given n cities and a list of flights, where flights[i] = [from, to, price] represents a directed flight. Starting from src, find the cheapest price to reach dst with at most k stops in between. Return -1 if no such route exists.

A "stop" is an intermediate city, so k = 1 means at most 2 edges are allowed. k = 0 means direct flight only.

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

With at most 1 stop, 0 → 1 → 3 costs 700. The cheaper 0 → 1 → 2 → 3 = 400 requires 2 stops and is rejected.

Input

n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1

Output

200

Explanation

0 → 1 → 2 uses 1 stop and costs 200.

Input

n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0

Output

500

Explanation

k = 0 forces the direct flight.

Intuition

Plain Dijkstra finds the absolute shortest path but ignores edge counts. Plain BFS minimizes edge count but ignores weights. This problem blends both: we want minimum weight subject to a hop budget.

Two insights unlock it:

State has two dimensions. The usual Dijkstra state (distance, city) is not enough — two routes to the same city with different remaining hop budgets are genuinely different. A cheaper route that used more hops is worse if it leaves us stranded.
Bellman-Ford is a perfect shape match. Bellman-Ford relaxes every edge in k + 1 rounds; round i discovers the cheapest walk using exactly i edges. For this problem we cap rounds at k + 1.

Modified Dijkstra (state (cost, city, stops_used)) gives the same answer with better average-case performance, since it prunes hopeless branches by cost. Both are correct; Bellman-Ford is simpler to reason about, Dijkstra is faster in practice.

Approach

BFS Brute Force

TimeO(V^k)

SpaceO(V^k)

Exhaustively explore every walk of length ≤ k + 1 from src using BFS layer by layer. Track the running cost. At the dst node, keep the minimum cost seen. Correct but explodes combinatorially — useful only as a sanity-check baseline for tiny inputs.

use std::collections::VecDeque;

impl Solution {
    pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
        let n = n as usize;
        let mut graph: Vec<Vec<(usize, i32)>> = vec![Vec::new(); n];
        for f in &flights {
            graph[f[0] as usize].push((f[1] as usize, f[2]));
        }

        // Layer-by-layer BFS; each entry is (city, cost).
        let mut best = i32::MAX;
        let mut queue: VecDeque<(usize, i32)> = VecDeque::new();
        queue.push_back((src as usize, 0));

        // 0..=k stops means 0..=k+1 edges.
        for _ in 0..=k {
            let size = queue.len();
            for _ in 0..size {
                let (city, cost) = queue.pop_front().unwrap();
                for &(next, price) in &graph[city] {
                    let new_cost = cost + price;
                    if new_cost >= best {
                        continue;
                    }
                    if next == dst as usize {
                        best = best.min(new_cost);
                    } else {
                        queue.push_back((next, new_cost));
                    }
                }
            }
        }

        if best == i32::MAX { -1 } else { best }
    }
}

Rust · runnable

function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number {
  const graph: Array<Array<[number, number]>> = Array.from({ length: n }, () => []);
  for (const [a, b, p] of flights) graph[a].push([b, p]);

  let best = Infinity;
  let queue: Array<[number, number]> = [[src, 0]];

  for (let stops = 0; stops <= k && queue.length > 0; stops++) {
    const next: Array<[number, number]> = [];
    for (const [city, cost] of queue) {
      for (const [neighbor, price] of graph[city]) {
        const newCost = cost + price;
        if (newCost >= best) continue;
        if (neighbor === dst) best = Math.min(best, newCost);
        else next.push([neighbor, newCost]);
      }
    }
    queue = next;
  }

  return best === Infinity ? -1 : best;
}

TypeScript · runnable

Bellman-Ford (K+1 rounds)

TimeO(K · E)

SpaceO(V)

Classical Bellman-Ford with a twist: we cap iterations at k + 1. Round i computes the cheapest walk using at most i edges. Critical detail — every round must read from a snapshot of the previous round's distances; otherwise a freshly updated neighbor could contribute two edges in the same round.

impl Solution {
    pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
        let n = n as usize;
        let inf = i32::MAX / 2;
        let mut dist = vec![inf; n];
        dist[src as usize] = 0;

        for _ in 0..=k {
            let snap = dist.clone();
            for f in &flights {
                let (u, v, w) = (f[0] as usize, f[1] as usize, f[2]);
                if snap[u] != inf && snap[u] + w < dist[v] {
                    dist[v]= snap[u] + w;
                }
            }
        }

        if dist[dst as usize] >= inf { -1 } else { dist[dst as usize] }
    }
}

Rust · runnable

function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number {
  const INF = Number.POSITIVE_INFINITY;
  let dist = new Array<number>(n).fill(INF);
  dist[src] = 0;

  for (let i = 0; i <= k; i++) {
    const snap= dist.slice();
    for (const [u, v, w] of flights) {
      if (snap[u] + w < dist[v]) dist[v]= snap[u] + w;
    }
  }

  return dist[dst]= INF ? -1 : dist[dst];
}

TypeScript · runnable

Modified Dijkstra

TimeO(E log E)

SpaceO(V · K)

Recommended

Standard Dijkstra state (cost, city) is insufficient — a cheaper route may have burned too many stops to finish. Extend the state to (cost, city, stops_used) and push to a min-heap ordered by cost.

Prune aggressively: for each city, track the minimum stops_used to reach it at any cost. A newly popped state whose stop count is worse than the recorded minimum cannot improve — skip it. The first pop at dst is optimal.

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
    pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
        let n = n as usize;
        let mut graph: Vec<Vec<(usize, i32)>> = vec![Vec::new(); n];
        for f in &flights {
            graph[f[0] as usize].push((f[1] as usize, f[2]));
        }

        // min-stops[city] = fewest edges ever used to reach city
        let mut min_stops = vec![i32::MAX; n];
        let mut heap: BinaryHeap<Reverse<(i32, usize, i32)>> = BinaryHeap::new();
        heap.push(Reverse((0, src as usize, 0)));

        while let Some(Reverse((cost, city, stops))) = heap.pop() {
            if city == dst as usize {
                return cost;
            }
            if stops > k || stops >= min_stops[city] {
                continue;
            }
            min_stops[city] = stops;
            for &(next, price) in &graph[city] {
                heap.push(Reverse((cost + price, next, stops + 1)));
            }
        }

        -1
    }
}

Rust · runnable

function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number {
  const graph: Array<Array<[number, number]>> = Array.from({ length: n }, () => []);
  for (const [a, b, p] of flights) graph[a].push([b, p]);

  // Simple binary min-heap on (cost, city, stops).
  const heap: Array<[number, number, number]> = [[0, src, 0]];
  const minStops = new Array<number>(n).fill(Infinity);

  const swap = (i: number, j: number) => {
    [heap[i], heap[j]] = [heap[j], heap[i]];
  };
  const up = (i: number) => {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p][0] <= heap[i][0]) break;
      swap(p, i);
      i= p;
    }
  };
  const down= (i: number)=> {
    const n= heap.length;
    while (true) {
      const l= i * 2 + 1;
      const r= l + 1;
      let best= i;
      if (l < n && heap[l][0] < heap[best][0]) best= l;
      if (r < n && heap[r][0] < heap[best][0]) best= r;
      if (best= i) break;
      swap(best, i);
      i= best;
    }
  };
  const push= (item: [number, number, number])=> {
    heap.push(item);
    up(heap.length - 1);
  };
  const pop= (): [number, number, number] | undefined=> {
    if (heap.length= 0) return undefined;
    const top= heap[0];
    const last= heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      down(0);
    }
    return top;
  };

  while (heap.length > 0) {
    const [cost, city, stops] = pop()!;
    if (city === dst) return cost;
    if (stops > k || stops >= minStops[city]) continue;
    minStops[city] = stops;
    for (const [next, price] of graph[city]) {
      push([cost + price, next, stops + 1]);
    }
  }

  return -1;
}

TypeScript · runnable

Trace

Bellman-Ford with k = 1 on the flights [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3:

round	snap[1]	snap[2]	snap[3]	relaxations	dist after
init	∞	∞	∞	—	[0, ∞, ∞, ∞]
1	∞	∞	∞	0→1: 100	[0, 100, ∞, ∞]
2	100	∞	∞	1→2: 200, 1→3: 700	[0, 100, 200, 700]

After k + 1 = 2 rounds, dist[3] = 700. The 200 + 200 = 400 route via 0 → 1 → 2 → 3 needs a third round, correctly excluded.

Edge cases

No path — if dst remains at infinity after k + 1 rounds, return -1.
src == dst — the problem guarantees they differ, but a defensive zero return is cheap.
Negative-weight edges — the problem fixes prices at ≥ 1, so we don't need Dijkstra's non-negativity check.
Self loops or parallel edges — both harmless; Bellman-Ford and heap-Dijkstra handle them.

💡

Tip

The "snapshot before relaxation" step is the classic bug. Without it, a single round can relax along two edges of a chain, violating the k-stop invariant.

Takeaway

When an optimization problem has a hard constraint on path length, extend your shortest-path state with that constraint and let the algorithm prune around it.

This pattern shows up directly in:

DEX arbitrage detection — Bellman-Ford over log-prices, where a negative cycle signals risk-free profit.
Network reliability routing — cheapest path subject to SLA hop limits in distributed systems.
Flight search backends — real-world airline APIs cap layovers similarly.

Hard#1192

Critical Connections in a Network

Tarjan’s bridge-finding algorithm. Must-know for systems interviews.

Hard#1489

Find Critical and Pseudo-Critical Edges in MST

Kruskal’s + edge classification. Deep graph understanding.

Hard#1579

Remove Max Edges to Keep Graph Traversable

Dual Union-Find. Process shared edges first (greedy).