Cheapest Flights Within K Stops

The problem

There are n cities, numbered 0 to n - 1. Each entry of flights is a one-way flight [from, to, price]. Find the cheapest trip from src to dst that makes at most k stops, and return its total price. A stop is a city where you change planes on the way, so src and dst are not stops, and a trip with k stops uses k + 1 flights. If no trip within the limit exists, return -1.

What to write

function solve(n: number, flights: number[][], src: number, dst: number, k: number): number

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

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

Output
500

Constraints

Each flight is [from,to,price] with positive price; cities are 0 through n-1.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   At most k stops means at most k + 1 flights. The limit matters: the cheapest route of all may use too many flights, and then a more expensive route is the answer. So one cheapest price per city is not enough. How many flights a price took matters too.

2. Hint 2: Ask a smaller question

   In example 1, write down the cheapest price to reach each city with one flight at most. Now use only that list and the flights to work out the prices with two flights at most. While you fill in the new list, which list must you read from?

3. Hint 3: Name the pattern

   Flights with different prices and a question about the cheapest route are the signal for a weighted shortest path. The limit on stops adds a twist: a route may use only so many flights. The Bellman-Ford algorithm, which improves the known prices in rounds over the whole flight list, fits: each round lets every route grow by one flight. Read the lesson on weighted shortest path.

4. Hint 4: State the invariant

   After round r, the price stored for a city is the cheapest way to reach it with at most r flights. A round reads only the prices of the round before and writes into a copy, so no route can gain two flights in one round.

5. Hint 5: Sketch the pseudocode

   Set every price to infinity and src's to 0. Repeat k + 1 times: copy the prices; for each flight [a, b, price], if old[a] + price is lower than copy[b], store it in copy[b]; then the copy becomes the prices. Return the price of dst, or -1 if it is infinity.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Perform k+1 relaxation rounds using a separate distance copy each round, preventing paths from using too many edges.

The slow way

Explore every route from src: take each flight out of the current city in turn, add its price, and stop when you reach dst or have used k + 1 flights. Return the lowest total that reached dst. It is correct, but every city can offer several flights, so each extra flight allowed multiplies the number of routes to explore.

The insight

Count flights, not cities. If you know the cheapest price to reach every city with at most r flights, one pass over the flight list gives the prices for at most r + 1 flights: each flight adds one leg to a route you already know. Start with only src reached, for free, and make k + 1 passes. These passes are the rounds of the Bellman-Ford algorithm.

Step by step

1. Mark every city as not reached, except src at a price of 0. These are the prices for trips with no flight at all: you are already at src and that costs nothing. Infinity stands for not reached, so any real price is lower.
2. Run k + 1 rounds, because k stops allow k + 1 flights. A round lets a route grow by one flight and no more. A trip with k stops has k + 1 flights, so that is the number of rounds needed, and one more would let in a forbidden trip.
3. Copy the prices; this round writes only into the copy. The old list must stay as it was while the round runs. A price written during this round already contains this round's flight, so reading it back would add a second flight in the same round.
4. Extend each route by one flight, reading only the old prices. The old price of the flight's start city plus the flight's price is a real trip with one more flight. The copy keeps that sum only if it is lower. This test is called relaxing the flight.
5. The copy becomes the prices for the next round. The copy now holds the cheapest price for every city with one more flight allowed. It is the old list that the next round reads from.
6. Return the price of dst, or -1 if it was never reached. After k + 1 rounds the price of dst is the cheapest trip with at most k + 1 flights. If it is still infinity, no allowed trip reaches dst.

The same numbered steps are the comments in each solution.

function solve(n, flights, src, dst, k) {
  // 1. Mark every city as not reached, except src at a price of 0
  let dist = Array(n).fill(Infinity);
  dist[src] = 0;
  // 2. Run k + 1 rounds, because k stops allow k + 1 flights
  for (let i = 0; i <= k; i++) {
    // 3. Copy the prices; this round writes only into the copy
    // [...dist] is a new array that holds the same values.
    const next = [...dist];
    // 4. Extend each route by one flight, reading only the old prices
    for (const [a, b, p] of flights)
      next[b] = Math.min(next[b], dist[a] + p);
    // 5. The copy becomes the prices for the next round
    dist = next;
  }
  // 6. Return the price of dst, or -1 if it was never reached
  return dist[dst] === Infinity ? -1 : dist[dst];
}

function solve(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number {
  // 1. Mark every city as not reached, except src at a price of 0
  let dist = Array(n).fill(Infinity);
  dist[src] = 0;
  // 2. Run k + 1 rounds, because k stops allow k + 1 flights
  for (let i = 0; i <= k; i++) {
    // 3. Copy the prices; this round writes only into the copy
    // [...dist] is a new array that holds the same values.
    const next = [...dist];
    // 4. Extend each route by one flight, reading only the old prices
    for (const [a, b, p] of flights) next[b] = Math.min(next[b], dist[a] + p);
    // 5. The copy becomes the prices for the next round
    dist = next;
  }
  // 6. Return the price of dst, or -1 if it was never reached
  return dist[dst] === Infinity ? -1 : dist[dst];
}

def solve(n, flights, src, dst, k):
    # 1. Mark every city as not reached, except src at a price of 0
    cost = [float("inf")] * n
    cost[src] = 0
    # 2. Run k + 1 rounds, because k stops allow k + 1 flights
    for _ in range(k + 1):
        # 3. Copy the prices; this round writes only into the copy
        updated = cost.copy()
        # 4. Extend each route by one flight, reading only the old prices
        for a, b, price in flights:
            updated[b] = min(updated[b], cost[a] + price)
        # 5. The copy becomes the prices for the next round
        cost = updated
    # 6. Return the price of dst, or -1 if it was never reached
    return -1 if cost[dst] == float("inf") else cost[dst]

Example 1, traced

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

Why it works

Before the first round the prices are right for trips with no flight: only src, at 0. Each round tries every flight on top of the old prices and keeps the lower price, so afterwards the prices are right for trips with one more flight at most. After k + 1 rounds they cover exactly the trips with at most k stops.

Time and space

Time O((k+1) E), extra space O(V). V is the number of cities, E of flights. There are k + 1 rounds, and each reads all E flights once: O((k+1) E) time. That leaves out copying V prices each round, which matters only when cities outnumber flights. Two lists of V prices exist at once: O(V) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Read the old prices, not the list you are writing. Updated in place, one list lets a route grow by several flights in a round: example 1 returns 400, the price of the trip with two stops, instead of 700.
• k counts stops, not flights: a trip with k stops has k + 1 flights, so run k + 1 rounds. With only k rounds, example 2, where k is 0, runs no round and returns -1 instead of 500.
• Do not return as soon as dst has a price: a later round may find a cheaper trip. In example 2 with k raised to 1, round 1 prices city 2 at 500 and round 2 lowers it to 200.

Pattern

Weighted shortest path. Builds on Network Delay Time.

Keep going