Find the Shortest Path in a Weighted Graph with Constraints
Last updated: February 21, 2025
Quick Overview
Given a weighted graph representing road segments, find the shortest path between two nodes subject to a maximum cost constraint (representing battery range).
Rivian
February 21, 202512
8
2,602 solved
Given a weighted graph representing road segments, find the shortest path between two nodes subject to a maximum cost constraint (representing battery range).
This is a vehicle-flavored graph problem that appears in Rivian coding rounds. It models the real problem of route planning with battery range constraints. The constraint twist makes standard Dijkstra insufficient and tests deeper algorithmic thinking.
What the Interviewer Expects
- Recognize this as a constrained shortest path problem
- Implement modified Dijkstra with state tracking for remaining budget
- Handle edge cases like unreachable nodes and zero-budget scenarios
- Optimize with pruning to avoid exploring dominated states
- Discuss the time complexity tradeoffs of different approaches
Key Topics to Cover
How to Approach This
- Clarify input constraints and edge cases before writing code.
- Walk through your approach verbally and confirm with the interviewer before coding.
- Start with a brute force solution, then optimize. Mention time and space complexity.
- Test your solution with examples, including edge cases like empty input or duplicates.
- Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.
Possible Follow-up Questions
- How would you add intermediate recharging stops that restore budget?
- What if edge weights change dynamically due to traffic?
- How would you return all paths within a small percentage of optimal?
- How does this relate to real EV route planning?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Problem Analysis
This problem requires finding the shortest path in a weighted graph while adhering to a maximum cost constraint, which represents the battery range of a vehicle. The classic Dijkstra's algorithm is ty...
Approach
- Initialization: Create a priority queue (min-heap) to store states represented by tuples of (current_distance, current_node, remaining_budget). Initialize the starting node with distance 0 and ...
Submit Your Answer
