Problem Description

You are given a network of n cities connected by flights. Each flight is represented as [from, to, price], indicating a direct flight from one city to another with a specific cost.

Your task is to find the cheapest way to travel from a source city src to a destination city dst, with the constraint that you can take at most k stops (intermediate cities) along the way.

Key Points:

• The flights array contains all available direct flights between cities
• Each flight has a fixed price and goes in one direction only
• You want to minimize the total cost of travel
• You can have at most k stops between source and destination (not counting the source and destination themselves)
• If no valid route exists within the stop limit, return -1

Example Scenario: If you have flights connecting cities 0→1 (cost 100), 1→2 (cost 100), and 0→2 (cost 500), and you want to go from city 0 to city 2 with at most 1 stop:

• Direct route: 0→2 costs 500
• Route with 1 stop: 0→1→2 costs 200
• The cheapest price would be 200

The solution uses a modified Bellman-Ford algorithm that relaxes edges exactly k+1 times to ensure we find the shortest path with at most k stops. The algorithm maintains an array dist where dist[i] represents the minimum cost to reach city i from the source. By iterating k+1 times and updating distances based on available flights, it finds the optimal path within the stop constraint.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves cities (nodes) connected by flights (edges), forming a graph structure.

Is it a tree?

• No: The graph can have multiple paths between cities and may contain cycles, so it's not a tree structure.

Is the problem related to directed acyclic graphs?

• No: While the flights are directed edges, the graph may contain cycles (you could potentially fly in circles between cities).

Is the problem related to shortest paths?

• Yes: We're looking for the cheapest (minimum cost) path from source to destination.

Is the graph weighted?

• Yes: Each flight has an associated cost/price, making this a weighted graph.

Dijkstra's Algorithm

• The flowchart leads us to Dijkstra's Algorithm for weighted shortest path problems.

However, there's an important constraint that modifies our approach: we need to limit the path to at most k stops. This constraint makes the problem slightly different from a standard shortest path problem. While the flowchart suggests Dijkstra's, the solution actually uses a modified Bellman-Ford algorithm (which can be viewed as a form of dynamic programming with controlled depth).

The connection to DFS: Although the provided solution uses Bellman-Ford, this problem can also be solved using DFS with memoization, where we explore all paths from source to destination while tracking the number of stops and pruning paths that exceed k stops. The DFS approach would backtrack when either reaching the destination, exceeding the stop limit, or encountering a more expensive path than previously found.

Conclusion: While the flowchart correctly identifies this as a weighted shortest path problem leading to Dijkstra's, the additional constraint of limiting stops makes modified Bellman-Ford or DFS with pruning more suitable approaches.

Intuition

The key insight is recognizing that this problem asks for the shortest path with a constraint on the number of edges (stops) we can traverse. This immediately suggests we need to track both the cost and the number of stops taken to reach each city.

Think of it this way: in a standard shortest path problem, we only care about the minimum cost to reach each node. But here, a path might be cheaper overall but use too many stops, making it invalid. Conversely, a more expensive path with fewer stops might be our only valid option.

The Bellman-Ford algorithm naturally fits this problem because it works by relaxing edges in iterations. Each iteration essentially extends paths by one more edge. If we run the algorithm for exactly k+1 iterations, we guarantee finding the shortest path that uses at most k+1 edges (which means at most k stops between source and destination).

Why k+1 iterations? Because:

• After 0 iterations: we only know the cost to the source (0)
• After 1 iteration: we know the best cost to cities reachable with direct flights
• After 2 iterations: we know the best cost to cities reachable with 1 stop
• After k+1 iterations: we know the best cost to cities reachable with k stops

The clever part of the implementation is using a backup array. During each iteration, we read costs from the backup (representing paths with one fewer edge) and write to the current array. This ensures that within a single iteration, we only extend paths by exactly one edge, preventing us from accidentally using results from the current iteration to further extend paths in the same iteration.

This approach guarantees we find the minimum cost path that respects our stop constraint, returning -1 if no such path exists within the limit.

Learn more about Depth-First Search, Breadth-First Search, Graph, Dynamic Programming, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The solution implements a modified Bellman-Ford algorithm to find the shortest path with at most k stops. Let's walk through the implementation step by step:

Initialization:

INF = 0x3F3F3F3F
dist = [INF] * n
dist[src] = 0

• We initialize a distance array dist where dist[i] represents the minimum cost to reach city i
• All cities start with infinite cost (INF), except the source city which has cost 0
• The value 0x3F3F3F3F is used as infinity - it's large enough to represent unreachable cities but small enough to avoid overflow when adding prices

Main Algorithm Loop:

for _ in range(k + 1):
    backup = dist.copy()
    for f, t, p in flights:
        dist[t] = min(dist[t], backup[f] + p)

The algorithm runs for exactly k + 1 iterations:

1. Create a backup: Before each iteration, we copy the current distance array. This backup represents the shortest distances using paths with one fewer edge.

2. Relax all edges: For each flight [from, to, price], we check if we can reach the destination city to more cheaply by taking this flight from city from. The key formula is:

   dist[to] = min(dist[to], backup[from] + price)

3. Why use backup? By reading from backup[from] instead of dist[from], we ensure that within a single iteration, we only extend paths by exactly one edge. This prevents us from using updated values from the current iteration, which would incorrectly allow paths with more edges than intended.

Example walkthrough:

• Iteration 0: Only source city has cost 0
• Iteration 1: Cities directly reachable from source get updated
• Iteration 2: Cities reachable with 1 stop get updated
• ...
• Iteration k+1: Cities reachable with k stops get updated

Return Result:

return -1 if dist[dst] == INF else dist[dst]

After k + 1 iterations, dist[dst] contains the minimum cost to reach the destination with at most k stops. If it's still infinity, no valid path exists within the stop limit.

Time Complexity: O((k + 1) × E) where E is the number of flights Space Complexity: O(n) for the distance array and its backup

Example Walkthrough

Let's walk through a concrete example to illustrate how the modified Bellman-Ford algorithm finds the cheapest price with limited stops.

Example Setup:

• Cities: 0, 1, 2, 3
• Flights: [[0,1,100], [1,2,100], [0,2,500], [1,3,200], [2,3,100]]
• Source: 0, Destination: 3, Maximum stops k: 1

We need to find the cheapest way from city 0 to city 3 with at most 1 stop.

Initialization:

dist = [0, INF, INF, INF]  // Only source (city 0) starts with cost 0

Iteration 1 (Direct flights from source):

• Create backup: backup = [0, INF, INF, INF]
• Process each flight:
  • Flight [0,1,100]: dist[1] = min(INF, 0 + 100) = 100
  • Flight [1,2,100]: dist[2] = min(INF, INF + 100) = INF (can't use, city 1 not reached in backup)
  • Flight [0,2,500]: dist[2] = min(INF, 0 + 500) = 500
  • Flight [1,3,200]: dist[3] = min(INF, INF + 200) = INF (can't use, city 1 not reached in backup)
  • Flight [2,3,100]: dist[3] = min(INF, INF + 100) = INF (can't use, city 2 not reached in backup)
• After iteration 1: dist = [0, 100, 500, INF]

Iteration 2 (Paths with 1 stop):

• Create backup: backup = [0, 100, 500, INF]
• Process each flight:
  • Flight [0,1,100]: dist[1] = min(100, 0 + 100) = 100 (no improvement)
  • Flight [1,2,100]: dist[2] = min(500, 100 + 100) = 200 (improved! Found 0→1→2 path)
  • Flight [0,2,500]: dist[2] = min(200, 0 + 500) = 200 (no improvement)
  • Flight [1,3,200]: dist[3] = min(INF, 100 + 200) = 300 (found 0→1→3 path)
  • Flight [2,3,100]: dist[3] = min(300, 500 + 100) = 300 (0→2→3 costs 600, worse than current)
• After iteration 2: dist = [0, 100, 200, 300]

Result: dist[3] = 300, so the cheapest price from city 0 to city 3 with at most 1 stop is 300.

The winning path is 0→1→3 (1 stop at city 1), costing 100 + 200 = 300.

Key Observations:

1. In iteration 1, we only discovered cities directly reachable from the source
2. In iteration 2, we discovered paths using exactly 1 stop
3. The backup array ensured we didn't chain multiple flights within the same iteration
4. The algorithm correctly found that 0→1→3 (300) is cheaper than the alternative 0→2→3 (600)

Solution Implementation

Time and Space Complexity

Time Complexity: O((k + 1) * m) where m is the number of flights (edges) and k is the maximum number of stops allowed.

The algorithm performs k + 1 iterations of the outer loop. In each iteration, it processes all m flights to update the distance array. Each flight update operation takes O(1) time (comparing and potentially updating the distance). Additionally, creating a backup copy of the distance array takes O(n) time per iteration, where n is the number of nodes. Therefore, the total time complexity is O((k + 1) * (n + m)). However, since in most practical cases m ≥ n - 1 for a connected graph, this can be simplified to O((k + 1) * m).

Space Complexity: O(n) where n is the number of nodes.

The algorithm uses two arrays: dist and backup, each of size n. The dist array stores the minimum distances from the source to all nodes, while backup is a temporary copy created in each iteration. No additional data structures scale with the input size, so the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Using a Backup Array

The Problem: A common mistake is trying to update the distance array in-place without creating a backup:

# INCORRECT implementation
for _ in range(k + 1):
    for f, t, p in flights:
        dist[t] = min(dist[t], dist[f] + p)  # Reading and writing to same array!

This approach fails because within a single iteration, we might use already-updated values from the current iteration. For example, if we update dist[1] early in the iteration and then use dist[1] to update dist[2] later in the same iteration, we've effectively considered a path with more edges than intended for this iteration.

The Solution: Always create a backup copy before each iteration and read from the backup while writing to the original:

# CORRECT implementation
for _ in range(k + 1):
    backup = dist.copy()
    for f, t, p in flights:
        dist[t] = min(dist[t], backup[f] + p)  # Read from backup, write to dist

Pitfall 2: Incorrect Iteration Count

The Problem: Using k iterations instead of k + 1:

# INCORRECT - only iterates k times
for _ in range(k):  # Wrong! This only allows k-1 stops
    backup = dist.copy()
    for f, t, p in flights:
        dist[t] = min(dist[t], backup[f] + p)

Remember that k represents the maximum number of stops (intermediate cities), not the number of edges. If you can have k stops, you can use up to k + 1 edges in your path.

The Solution: Always iterate k + 1 times to allow for paths with up to k + 1 edges:

# CORRECT - iterates k+1 times
for _ in range(k + 1):  # Allows exactly k stops (k+1 edges)
    backup = dist.copy()
    for f, t, p in flights:
        dist[t] = min(dist[t], backup[f] + p)

Pitfall 3: Integer Overflow with Infinity Value

The Problem: Using float('inf') or sys.maxsize can cause issues:

# Potentially problematic
dist = [float('inf')] * n  # Can cause comparison issues
# or
dist = [sys.maxsize] * n   # Might overflow when adding prices

When adding prices to infinity values, you might encounter overflow or unexpected behavior in comparisons.

The Solution: Use a large but reasonable value like 0x3F3F3F3F (approximately 10^9):

# CORRECT - safe infinity value
INF = 0x3F3F3F3F  # Large enough but won't overflow
dist = [INF] * n

This value is large enough to represent unreachable cities but small enough that adding typical flight prices won't cause overflow issues.