A Bellman-Ford Variation - LeetCode 787 - Cheapest Flights Within K Stops

When studying shortest path problems, the first algorithm most people encounter is usually Dijkstra’s algorithm. I also started by looking into a Dijkstra-based approach, but after digging into the underlying mechanics, I realized that this particular problem is actually a much better fit for a slightly modified version of the Bellman-Ford algorithm rather than applying a standard shortest path algorithm directly.

Problem Link & Overview: What Was the Problem?

Problem Link: 787. Cheapest Flights Within K Stops
Summary: Given n cities and a list of flights with their prices, the goal is to find the cheapest cost from a source city (src) to a destination city (dst). However, there is an additional constraint: you can make at most K stops along the way. In other words, you can take at most K + 1 flights in total.

Approach: How Did I Try to Solve It at First?

When I first studied the problem, I naturally considered using Dijkstra’s algorithm. However, Dijkstra becomes a bit tricky when you have to keep track of an additional constraint like “how many flights have been taken so far.” Since it always prioritizes the currently cheapest accumulated cost through a priority queue, things can become complicated if you only discover later that the number of stops has exceeded the allowed limit.

On the other hand, the Bellman-Ford approach—where one complete pass over all flight routes is treated as a single “round”—makes the logic much cleaner.

Round 1: Compute the minimum cost to cities reachable with exactly one flight from the source.
Round 2: Using the results from Round 1, compute the minimum cost to cities reachable with two flights (one stop).

By repeating this process, we only need to perform exactly K + 1 rounds before stopping, making the stop constraint very intuitive to manage.

Bellman-Ford is generally considered to have a relatively heavy time complexity, but in this problem, K is usually much smaller than the number of cities. Because of that, I felt that this Bellman-Ford variation was actually a cleaner solution than trying to adapt Dijkstra with additional state management and the overhead of a priority queue.

Troubleshooting: What Issues Did I Run Into?

There was one subtle issue that required careful attention while turning the idea into actual code.

1. Results Being Propagated Within the Same Round

If I used only a single shortest-distance array (dist), a structural bug could occur during one iteration.

As I iterate through all flight routes in Round 1, some cities get updated before others. Later in the same iteration, there may be another flight whose departure city happens to be one that was just updated.

If that happens, a route that should have been evaluated in the next round ends up being calculated immediately within the current round. In other words, the algorithm accidentally chains together an extra flight within the same iteration, causing the stop count to exceed the intended limit.

Solution: I decided to maintain two separate distance maps:

dist1: the stable map containing results completed up to the previous round.
dist2: a temporary map that stores the newly calculated results for the current round.

Since updates made during the current round are written only to dist2, they cannot immediately affect other calculations in the same iteration. This completely prevents the chain-reaction problem. Once the round finishes, I simply overwrite the previous map with the new one (dist1 = dist2) and move on to the next round. (Of course, the copy operation itself also comes with a cost.)

Final Implementation: How Did I Solve It?

Based on the approach above, I implemented the following C++ solution, which was ultimately accepted by LeetCode.

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        // Initialize distance arrays with INT_MAX.
        vector<int> dist1(n, INT_MAX);
        vector<int> dist2(n, INT_MAX);

        // The cost to reach the source is always zero.
        dist1[src] = 0;
        dist2[src] = 0;

        int count = k + 1;
        while (count--) {
            for (auto& flight : flights) {
                int from = flight[0];
                int to = flight[1];
                int price = flight[2];

                // Only expand from cities that were reachable
                // in the previous round.
                if (dist1[from] < INT_MAX) {
                    int newPrice = dist1[from] + price;

                    // Update only if the new route is cheaper.
                    if (newPrice < dist2[to]) {
                        dist2[to] = newPrice;
                    }
                }
            }

            // The current round is complete,
            // so promote the new map to the previous map.
            dist1 = dist2;
        }

        // If the destination is still unreachable, return -1.
        return dist2[dst] == INT_MAX ? -1 : dist2[dst];
    }
};

Summary & Reflection

This problem gave me an opportunity to think about how the characteristics of a constraint—in this case, the K-stop limit—can influence the choice of algorithm. Instead of mechanically applying a well-known shortest path algorithm, it was interesting to consider which underlying mechanism actually matched the structure of the problem.

Later on, I also spent some time discussing the problem with Gemini, which helped me understand this Bellman-Ford variation even more deeply.