Introduction

Cheapest Flights Within K Stops is one of the most popular shortest path interview problems.

You are given:

nflights[][]
src
dst
k

Goal:

Find minimum cost from source to destination
with at most k stops.

If destination cannot be reached:

Return -1

Example

Input:

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

Output:

500

Key Observation

Normal Dijkstra only cares about:

Minimum Cost

This problem also cares about:

Number of Stops

Therefore we must track:

(node, cost, stops)

Algorithm

1. Build graph2. Push source into min heap
3. Store cost and stops
4. Explore neighbors
5. Ignore paths exceeding k stops
6. Return minimum cost

Dry Run

Graph:

0 → 1 (100)
1 → 2 (100)
2 → 3 (100)
0 → 3 (500)

Allowed:

k = 1

Path:

0 → 3
Cost = 500

Answer:

500

Approach : Modified Dijkstra

Explanation

For every state:

  1. Store current node.
  2. Store current cost.
  3. Store stops used.
  4. Expand neighbors.
  5. Ignore paths with too many stops.

Practice

Complexity Analysis

Time Complexity: O(E log V)
Space Complexity: O(V + E)

Why This Problem is Important

  • Dijkstra Algorithm
  • Priority Queue
  • Graph Traversal
  • Shortest Path
  • State-Based Search

Common Beginner Mistakes

  • Ignoring stop count
  • Using normal Dijkstra directly
  • Returning expensive route
  • Wrong stop calculation
  • Missing destination check

Interview Tip

Always explain:

State = (node, cost, stops)

This is the main difference from normal Dijkstra.

Related Questions

  • Dijkstra Algorithm
  • Network Delay Time
  • Path With Minimum Effort
  • Bellman Ford Algorithm

Final Takeaway

Cheapest Flights Within K Stops is a modified shortest path problem.

It teaches:

  • State-Based Graph Traversal
  • Priority Queue Usage
  • Dijkstra Variations
  • Path Constraints

Mastering this problem makes advanced shortest path interview questions significantly easier.