[NEW] Add solution for Flight Routes #138
Description
🎯 Problem Information
- Problem Name: Flight Routes
- CSES Link: https://cses.fi/problemset/task/1196
- Category: graph algorithms
- Estimated Difficulty: [Medium]
📋 Problem Description
We are given a directed weighted graph representing flight connections between cities.
Our task is to find the k shortest distinct routes from city 1 Syrjälä to city n Metsälä.
A route may visit the same city multiple times, and if multiple routes have the same cost, all should be considered individually.
💡 Proposed Approach
Describe the algorithm/approach you plan to use:
We can extend Dijkstra’s algorithm to find the k shortest paths using a priority queue (min-heap):
- Maintain a min-heap of {distance, node} pairs.
- For each node, store up to k smallest distances (in a vector or priority queue).
- Each time we pop a node from the heap:
If this is the k-th time reaching the destination node, we stop.
Otherwise, we relax all its outgoing edges as in Dijkstra’s algorithm, pushing new potential distances into the heap.
This ensures we explore paths in increasing order of total cost, and since k ≤ 10, we avoid excessive memory or computation.
- Time Complexity: O(m * log(n * k))
- Space Complexity: O(n * k)
📝 Implementation Notes
Any special considerations or optimizations needed:
- Requires fast I/O
- Needs modular arithmetic
- Large input constraints
- Edge cases to consider
🏷️ Labels
Please add appropriate labels:
-
hacktoberfest(if contributing during Hacktoberfest) -
good first issue(if suitable for beginners) -
help wanted(if you need assistance)
👤 Assignee
- I would like to work on this issue
- I'm available for guidance/review
📎 Additional Context
The problem can be solved using a modified multi-path Dijkstra approach rather than Yen’s algorithm, as we only need k ≤ 10 shortest paths, not all.
This makes it efficient for large graphs within the given time limits.