Cheapest flights within K stops

Why it matters

An airline sells you a ticket from city A to city D. You want the lowest price, but you also do not want more than two stops, because each stop costs time and risks a missed connection. The cheapest flight is not always the one with the fewest stops, and the fewest-stops flight is not always the cheapest. You need the cheapest price among trips that respect a limit on stops.

This problem is a shortest-path problem with one extra rule. The graph has cities as vertices and flights as directed edges with a price as the weight. The rule is that the path may use only a limited number of edges. Plain Dijkstra's algorithm finds the cheapest path with no limit, so it does not solve this problem directly. This lesson uses the Bellman-Ford method from the earlier lesson in this module, and changes it so that it counts rounds. You will see why each round must read a copy of the previous round's results, and what goes wrong without the copy.

Two words are used in a precise way here. A flight is one edge, one trip from one city to the next. A stop is a city you pass through between the start and the destination. A trip with K stops therefore uses K + 1 flights. Most people count stops, but the code counts flights, so keep the difference in mind from the start.

A small example

Look at four cities numbered 0 to 3. There are four flights:

• 0 to 1, price 100
• 1 to 2, price 100
• 2 to 3, price 100
• 0 to 3, price 500

You want to go from city 0 to city 3. The direct flight costs 500 and has zero stops. The chain 0 to 1 to 2 to 3 costs 300 in total and has two stops, which means three flights.

Now check the answer for each limit:

• With 0 stops (one flight at most), you must take the direct flight. The answer is 500.
• With 1 stop (two flights at most), the chain needs three flights, so it is not allowed. The answer is still 500.
• With 2 stops (three flights at most), the chain is allowed. The answer is 300.

The limit changes the answer. A plain shortest-path search would return 300 for every limit, because it does not know about the limit. You need an algorithm that stops after a set number of flights.

The idea: count flights in rounds

Bellman-Ford works in rounds. In each round, it looks at every flight once. For each flight from city u to city v with price p, it asks: can I reach v more cheaply by going through u? If yes, it lowers the best known price to v.

The key fact is this. After round 1, the best known prices use at most one flight. After round 2, they use at most two flights. After round r, every best known price uses at most r flights. Each round adds exactly one more flight to the longest allowed trip.

So for a limit of K stops, you need K + 1 flights, which means K + 1 rounds. Run exactly that many rounds and stop. The price to the destination after the last round is the answer.

Keep a list dist where dist[c] is the cheapest known price to reach city c. Start with dist[src] = 0 and every other entry set to a very large number meaning "not reached yet". Use std::numeric_limits<long long>::max() / 4 for that very large number. Dividing by 4 leaves room so that an addition near it does not overflow. The code also skips any flight that starts from an unreached city, so the large number is never added to a price.

Bellman-Ford with a copy each round

Here is the first version of the function. It runs K + 1 rounds and reads each round from a copy of the previous round's values.

#include <limits>
#include <utility>
#include <vector>
 
struct Flight {
    int from;
    int to;
    int price;
};
 
constexpr long long INF = std::numeric_limits<long long>::max() / 4;
 
// Returns the cheapest price from src to dst using at most k stops, or -1.
long long cheapest_bellman_ford(int n, const std::vector<Flight>& flights,
                                int src, int dst, int k) {
    std::vector<long long> dist(n, INF);
    dist[src] = 0;
    for (int round = 0; round <= k; ++round) {
        std::vector<long long> next = dist;  // this round reads only last round values
        for (const Flight& f : flights) {
            if (dist[f.from] == INF) continue;
            long long candidate = dist[f.from] + f.price;
            if (candidate < next[f.to]) next[f.to] = candidate;
        }
        dist = std::move(next);
    }
    return dist[dst] == INF ? -1 : dist[dst];
}

Read the loop carefully. The outer loop runs k + 1 times because the condition is round <= k and round starts at 0. Inside each round, next starts as a copy of dist. The inner loop reads dist[f.from], which is the value from before this round. It writes into next[f.to]. At the end of the round, dist takes the new values.

The copy is what makes the count correct. std::move hands the contents of next to dist without copying them again. The next section shows what happens without it.

Why each round must read a copy

Suppose you skip the copy and update dist in place, so each change is visible to later flights in the same round. The code would look like this:

// Wrong: one round can chain several flights.
for (const Flight& f : flights) {
    if (dist[f.from] == INF) continue;
    long long candidate = dist[f.from] + f.price;
    if (candidate < dist[f.to]) dist[f.to] = candidate;
}

Take this chain of three flights: 0 to 1 at price 1, 1 to 2 at price 1, and 2 to 3 at price 1. The flights are listed in that order. Ask for the cheapest trip from 0 to 3 with at most K = 1 stop. That means at most two flights, so the correct answer is -1, because the trip needs three flights.

Trace the in-place version with K = 1, which runs two rounds. In round 1, the first flight sets dist[1] = 1. The second flight then reads that new value and sets dist[2] = 2. The third flight reads that and sets dist[3] = 3. All three flights were used in round 1, so the limit of two flights was broken without anyone noticing. Round 2 changes nothing. The wrong code returns 3.

With the copy, round 1 can only set prices for one flight from the starting values. Round 1 sets dist[1] = 1 and nothing else. Round 2 sets dist[2] = 2. The city 3 is never reached in two rounds, so dist[3] stays at INF and the function returns -1.

Here is a program that runs both versions on this chain, plus the four-city example. It was compiled with g++ -std=c++20 -Wall on g++ 15.2 and the output below is what it printed.

#include <iostream>
#include <limits>
#include <utility>
#include <vector>
 
struct Flight {
    int from;
    int to;
    int price;
};
 
constexpr long long INF = std::numeric_limits<long long>::max() / 4;
 
long long cheapest_bellman_ford(int n, const std::vector<Flight>& flights,
                                int src, int dst, int k) {
    std::vector<long long> dist(n, INF);
    dist[src] = 0;
    for (int round = 0; round <= k; ++round) {
        std::vector<long long> next = dist;
        for (const Flight& f : flights) {
            if (dist[f.from] == INF) continue;
            long long candidate = dist[f.from] + f.price;
            if (candidate < next[f.to]) next[f.to] = candidate;
        }
        dist = std::move(next);
    }
    return dist[dst] == INF ? -1 : dist[dst];
}
 
long long cheapest_in_place(int n, const std::vector<Flight>& flights,
                            int src, int dst, int k) {
    std::vector<long long> dist(n, INF);
    dist[src] = 0;
    for (int round = 0; round <= k; ++round) {
        for (const Flight& f : flights) {
            if (dist[f.from] == INF) continue;
            long long candidate = dist[f.from] + f.price;
            if (candidate < dist[f.to]) dist[f.to] = candidate;
        }
    }
    return dist[dst] == INF ? -1 : dist[dst];
}
 
int main() {
    std::vector<Flight> line = {{0, 1, 100}, {1, 2, 100}, {2, 3, 100}, {0, 3, 500}};
    for (int k = 0; k <= 2; ++k) {
        std::cout << "k=" << k << "  answer=" << cheapest_bellman_ford(4, line, 0, 3, k) << "\n";
    }
    std::vector<Flight> chain = {{0, 1, 1}, {1, 2, 1}, {2, 3, 1}};
    std::cout << "chain k=1 with copy=" << cheapest_bellman_ford(4, chain, 0, 3, 1)
              << " in place=" << cheapest_in_place(4, chain, 0, 3, 1) << "\n";
    std::cout << "chain k=2 with copy=" << cheapest_bellman_ford(4, chain, 0, 3, 2) << "\n";
}

Output:

k=0  answer=500
k=1  answer=500
k=2  answer=300
chain k=1 with copy=-1 in place=3
chain k=2 with copy=3

The first three lines match the table in the small example. The chain line shows the bug: the in-place version reports a trip that uses three flights when only two are allowed.

A second way: go level by level

The same idea can be written as a breadth-first search, where each level of the search is one flight. Level 1 holds the cities reached by one flight, level 2 holds those reached by two flights, and so on. The difference from the plain breadth-first search you may have seen is that a city can be reached again at a lower price on a later level. So the search keeps the best price for each city, and only expands a city again when its price has improved.

The search keeps two lists. best holds the cheapest known price to each city. frontier holds the cities whose best price changed in the last level. Only those cities can produce a new improvement, because the others were already expanded with the same price. Here is the code:

#include <limits>
#include <utility>
#include <vector>
 
struct Flight {
    int from;
    int to;
    int price;
};
 
constexpr long long INF = std::numeric_limits<long long>::max() / 4;
 
long long cheapest_by_levels(int n, const std::vector<Flight>& flights,
                             int src, int dst, int k) {
    std::vector<std::vector<std::pair<int, int>>> out(n);
    for (const Flight& f : flights) out[f.from].push_back({f.to, f.price});
 
    std::vector<long long> best(n, INF);
    best[src] = 0;
    std::vector<int> frontier{src};
 
    for (int level = 0; level <= k && !frontier.empty(); ++level) {
        std::vector<long long> next = best;
        std::vector<int> changed;
        std::vector<bool> queued(n, false);
        for (int city : frontier) {
            for (auto [to, price] : out[city]) {
                long long candidate = best[city] + price;
                if (candidate < next[to]) {
                    next[to] = candidate;
                    if (!queued[to]) {
                        queued[to] = true;
                        changed.push_back(to);
                    }
                }
            }
        }
        best = std::move(next);
        frontier = std::move(changed);
    }
    return best[dst] == INF ? -1 : best[dst];
}

The loop runs for k + 1 levels, the same count as the rounds in Bellman-Ford. Level 0 starts from the source, so it covers trips with one flight. The loop stops early when the frontier is empty, because no city improved and no further trip can be cheaper.

The code reads best[city] while it fills next, so the expansions in one level use the previous level's prices. This is the same copy rule as before. The queued list stops a city from being added to changed twice in one level, which keeps the work small.

The level version returns the same answers as the round version. The graph from the small example gives 500, 500 and 300 for k equal to 0, 1 and 2.

A harder example: the cheap route has more flights

The first example had one cheap route and one expensive route. Real searches have trips where the cheapest route has the most flights, so the answer changes in a less obvious way. Take five cities numbered 0 to 4 and find the cheapest trip from 0 to 4:

• Route A: 0 to 1 at 50, then 1 to 4 at 50. Two flights, total 100.
• Route B: 0 to 2 at 10, then 2 to 3 at 10, then 3 to 4 at 10. Three flights, total 30.
• Route C: 0 to 4 directly at 200. One flight.

Route B is the cheapest, but it has three flights, which is two stops. The table shows which route wins at each limit.

Notice that the answer never goes up as the limit rises. A larger limit only adds choices. A common off-by-one mistake treats k as the number of flights instead of stops. That version allows only 2 flights when k = 2, so it returns 100 and misses route B, which costs 30. The round-based method runs K + 1 rounds, so it sees route B in round 3.

Here are the two functions from the first program, run on this graph. The main function is the only new part:

int main() {
    std::vector<Flight> f = {{0, 1, 50}, {1, 4, 50}, {0, 2, 10}, {2, 3, 10}, {3, 4, 10}, {0, 4, 200}};
    for (int k = 0; k <= 3; ++k) {
        std::cout << "k=" << k << " answer=" << cheapest_bellman_ford(5, f, 0, 4, k)
                  << " in-place=" << cheapest_in_place(5, f, 0, 4, k) << "\n";
    }
}

Output:

k=0 answer=200 in-place=30
k=1 answer=100 in-place=30
k=2 answer=30 in-place=30
k=3 answer=30 in-place=30

The copy version gives the table's answers. The in-place version returns 30 for k = 0, which means it used all three flights of route B when only one flight was allowed. Compare that with the table. The bug shows up on the first row, and it is easy to miss if you only test the largest limit.

Checking the answers

A good habit is to compare a fast method with a slow method that is easy to trust. The slow method here tries every path with at most k + 1 flights, by depth-first search, and keeps the cheapest. For small random graphs, that is fast enough.

The test made 3000 random graphs with between 2 and 7 cities, up to 13 flights, prices from 1 to 20, and limits from 0 to 3. Each graph was checked against the slow method for both cheapest_bellman_ford and cheapest_by_levels. The run printed mismatches=0 of 3000.

This check does not prove the code is correct, but it catches the kinds of mistake that matter here: an off-by-one count of flights, a missing copy, and a wrong return value for unreachable cities.

Common mistakes

Using k rounds instead of k + 1. This is the most common error. K stops means K + 1 flights. With k rounds, a trip with one flight and no stops is still found, but the trip with K stops and K + 1 flights is missed. On the small example with k = 2, three rounds are needed. Running only two rounds returns 500 instead of 300.

Forgetting the copy. The in-place version above returns 3 on the chain example where -1 is correct. The code looks almost the same, and the bug only shows when a path is long enough to be cut off by the limit. Test with a chain longer than the limit.

Returning INF instead of -1. If the destination was never reached, dist[dst] still holds INF, a huge number. Printing it gives a meaningless price. Check for INF and return -1, or whatever value the problem asks for.

Adding to INF. Adding a price to INF is safe in this lesson, because INF is max / 4 and the code skips unreached cities. If you use std::numeric_limits<long long>::max() as the large number, the addition can overflow. The result wraps to a negative number, and a bad path looks cheap. Use a large number divided by 4, or check before adding.

Using a narrow type for prices. A price written with a decimal point is not an int. If you write Flight f{0, 1, 2.5};, g++ stops with this error:

narrow.cpp: In function ‘int main()’:
narrow.cpp:4:20: error: narrowing conversion of ‘2.5e+0’ from ‘double’ to ‘int’ [-Wnarrowing]
    4 |     Flight f{0, 1, 2.5};
      |                    ^~~

The braces { } refuse to drop the decimal part silently. Either use whole numbers, or change the field type on purpose.

Mixing up the source and destination in the flight list. Each flight is {from, to, price}. A flight from 0 to 1 is {0, 1, 100}, not {1, 0, 100}. Flights in the list are one-way, so reversing them changes the answer.

Practice

Exercise 1. Use the four-city example. What does cheapest_bellman_ford return for k = 3, and why?

Show the answer

It returns 300. With k = 3, up to four flights are allowed. The chain of three flights is allowed, and it is cheaper than the direct flight at 500.

Exercise 2. How many rounds does cheapest_bellman_ford run when k = 5?

Show the answer

It runs 6 rounds. The loop starts at 0 and runs while round <= k, so it covers the values 0, 1, 2, 3, 4 and 5. Each round allows one more flight, so 6 rounds allow up to 6 flights, which is 5 stops.

Exercise 3. On the chain example with flights 0 to 1, 1 to 2 and 2 to 3, each price 1, what is the answer for k = 0, and what is the answer for a trip from city 2 to city 2 with k = 0?

Show the answer

For k = 0, the answer from 0 to 3 is -1, because the trip needs three flights and only one is allowed. The trip from city 2 to city 2 costs 0. The starting city is already the destination, so no flight is needed, and the code sets dist[src] = 0 before any round.

Exercise 4. Change cheapest_by_levels so it also returns -1 when k is negative. Why is that check needed?

Show the answer

Add a check at the top of the function, for example if (k < 0) return -1;. With a negative k, the loop condition level <= k is false from the start, so frontier is never expanded, and best[dst] stays at INF unless dst is src. Without the check, the answer for a negative limit is confusing: it is -1 for most pairs, but 0 for a trip from a city to itself. An explicit check makes the rule clear. Whether a negative limit should be allowed at all is a question for the problem statement.

Exercise 5. A flight list has 1000 flights, 200 cities, and k = 3. Roughly how many flight checks does cheapest_bellman_ford make in total?

Show the answer

It makes about 4 rounds times 1000 flights, which is 4000 checks. Each round also copies the 200-entry dist list, which is 800 copies in total. The count does not depend on the number of cities except for those copies. The level version can do less work, because it only checks flights from cities that changed in the last level.

Summary

• A trip with K stops uses at most K + 1 flights, so the search must run K + 1 rounds or levels.
• Each Bellman-Ford round allows one more flight, so after round r the best prices use at most r flights.
• Each round must read the previous round's values from a copy. Updating in place lets one round chain several flights and breaks the limit.
• A level-by-level search gives the same answers, and it only expands cities whose price improved in the last level.
• Return -1 for an unreachable destination, and never add to a large number that can overflow.
• Test against a slow method that tries every short path, using random small graphs.