Given a weighted directed graph with n nodes and a list of edges where each edge has a positive weight, explain how you would find the shortest path from a source node to all other nodes.
For example:
n = 5, edges = [[0,1,4], [0,2,1], [2,1,2], [1,3,1], [2,3,5], [3,4,3]] Source = 0
Shortest distances: {0: 0, 1: 3, 2: 1, 3: 4, 4: 7} Path to node 1: 0 -> 2 -> 1 (cost 1 + 2 = 3), which is shorter than the direct edge 0 -> 1 (cost 4).
What algorithm is best suited for this? Why does it work? What assumption about edge weights is required?
Explain your approach and analyze the time and space complexity.
How to approach it
- Hint 1
Dijkstra's algorithm is the standard approach for shortest paths with non-negative edge weights.
- Hint 2
Use a priority queue (min-heap) to always process the node with the smallest known distance next. This greedy choice is optimal because all edge weights are non-negative.
- Hint 3
For each node pulled from the heap, relax its neighbors: if the path through the current node is shorter than the known distance, update it and add to the heap.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.