787. Cheapest Flights Within K Stops

At a Glance

Topic: graphs
Pattern: Bellman-Ford / layered relaxation (shortest-path family)
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Meta, Bloomberg
Frequency: High
LeetCode: 787

Directed weighted flights among n cities. Find the cheapest price from src to dst when you may use at most k stops (each stop is an intermediate city; the usual Bellman–Ford layer trick relaxes for k+1 edge layers).

Recognition Cues

Edge constraints on number of edges used — Bellman-Ford limited rounds
Negative weights absent — BF rounds sufficient

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

State BFS (city, stops) — okay memory.
Optimal — copy DP array each round like BF k+1 iterations — O(E·k) time.

Optimal Solution

Go

func findCheapestPrice(nodeCount int, flights [][]int, source int, destination int, maxStops int) int {
	const infinity = 1 << 30
	prices := make([]int, nodeCount)
	for index := range prices {
		prices[index] = infinity
	}
	prices[source] = 0
	for round := 0; round <= maxStops; round++ {
		nextPrices := append([]int(nil), prices...)
		for _, flight := range flights {
			from := flight[0]
			to := flight[1]
			cost := flight[2]
			if prices[from] == infinity {
				continue
			}
			candidate := prices[from] + cost
			if candidate < nextPrices[to] {
				nextPrices[to] = candidate
			}
		}
		prices = nextPrices
	}
	if prices[destination] >= infinity {
		return -1
	}
	return prices[destination]
}

JavaScript

function findCheapestPrice(nodeCount, flights, source, destination, maxStops) {
  const infinity = Number.POSITIVE_INFINITY;
  let prices = new Array(nodeCount).fill(infinity);
  prices[source] = 0;
  for (let round = 0; round <= maxStops; round += 1) {
    const nextPrices = [...prices];
    for (const flight of flights) {
      const [from, to, cost] = flight;
      if (prices[from] === infinity) {
        continue;
      }
      const candidate = prices[from] + cost;
      if (candidate < nextPrices[to]) {
        nextPrices[to] = candidate;
      }
    }
    prices = nextPrices;
  }
  return prices[destination] === infinity ? -1 : prices[destination];
}

Walkthrough

Round r represents routes using up to r edges from prior layer cost snapshot — prevents using same edge layer trick incorrectly by scanning fresh nextPrices each round.

Invariant: After maxStops+1 rounds, best price using ≤ maxStops intermediate vertices is captured.

Edge Cases

No route — -1
Direct flight beats multi-hop

Pitfalls

Mixing Bellman rounds without copying prior layer — allows extra hops within same round

Variants

Exactly k stops — adjust rounds equality

Mind-Map Tags

#bellman-ford #layered-relaxation #flights #shortest-path