Problem 26.3 · Shortest PathsMedium

Cheapest Flights Within K Stops

PatternDijkstra's Shortest Path 1D Dynamic Programming

What it teaches: Bellman-Ford limited to k + 1 edges, relaxing from a copy each round.

Practise it on judges as “Cheapest Flights Within K Stops”.

The problem

flights[i] = [from, to, price]. Return the cheapest price from src to dst using at most k stops (k + 1 flights), or −1.

Example 1

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

Constraints

1 ≤ n ≤ 100
0 ≤ k < n

Pattern clues in the wording

→ Cheapest path with a limit on the number of edges

These clues point to Dijkstra's Shortest Path: Always expand the closest unfinished node from a min-heap; with non-negative weights, its distance is final.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        return -1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 4 flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]] src = 0 dst = 3 k = 1	700
2	n = 3 flights = [[0,1,100],[1,2,100],[0,2,500]] src = 0 dst = 2 k = 1	200
3	n = 3 flights = [[0,1,100],[1,2,100],[0,2,500]] src = 0 dst = 2 k = 0	500

From slow to fast

Approaches

1. k + 1 rounds of Bellman-Ford · O(k × E)

k + 1 rounds of Bellman-Ford

Time O(k × E) Space O(n)

dist[src] = 0. Repeat k + 1 times: next = copy of dist; relax every flight from dist into next; dist = next.

Approach 1

import java.util.Arrays;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int INF = Integer.MAX_VALUE;
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int round = 0; round <= k; round++) {
            int[] next = dist.clone();
            for (int[] f : flights) {
                if (dist[f[0]] == INF) continue;
                next[f[1]] = Math.min(next[f[1]], dist[f[0]] + f[2]);
            }
            dist = next;
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
}

Verdict: The copy enforces the flight limit.

Before you submit

Edge cases and common mistakes

Test these inputs

k = 0 (direct flight only)
No route

Mistakes people make

Relaxing in place, which lets one round use several flights.

Interview

Follow-up questions

Can Dijkstra work?

Command Palette

The problem

Approaches

k + 1 rounds of Bellman-Ford

Edge cases and common mistakes

Follow-up questions