Coding · Graphs and grids
Shortest path with Dijkstra
- Reported once
- Medium
- campus (SDE-1 level)
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
A network has nodes labelled 1 to n, and each directed edge [from, to, time] says a signal sent from one node reaches the other after that many time units. A signal starts at node k and travels along every outgoing edge at once; return how long it takes until every node has received it, or -1 if some node is never reached. For times [[1,2,1],[1,3,5],[2,3,2],[3,4,1]], n = 4 and k = 1 the answer is 4. Times are non-negative, and there can be tens of thousands of nodes and about 100,000 edges.
Restated in our own words, not a quote from Zomato or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: are the edges directed, and can there be several edges between the same pair of nodes, or an edge from a node to itself? Can a time be zero or negative? Are the labels exactly 1 to n with no gaps? How many nodes and edges are there, so I know whether an O(V×E) method is allowed? What should I return when n is 1 and there are no edges, or when some node cannot be reached?
I would assume directed edges, non-negative integer times, possible duplicate edges and self loops, an answer of 0 for a single node, and -1 when any node is unreachable.
Brute force
Say the obvious answer and why it is too slow.
The direct answer is Bellman-Ford. Set the distance of node k to 0 and everything else to infinity, then repeat n - 1 times: go through every edge and lower the distance of its target if the route through its source is shorter. The largest distance is the answer. It works for every weight, but it costs O(V×E).
With 10,000 nodes and 100,000 edges that is a billion edge checks, and most passes change almost nothing, because only a thin frontier of nodes still has a distance that can improve. Another naive idea, a depth-first search that keeps the smallest time seen per node, can revisit nodes an exponential number of times on a layered graph. Both waste work that a smarter visiting order avoids.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(V×E)
- Time
- O(E log E)
- Space
- O(V + E)
The pattern is Dijkstra's algorithm with a min-heap. Keep a heap of candidate arrivals, each a pair (time, node), starting with (0, k). Repeatedly take the pair with the smallest time. If that node is already settled, skip the pair. Otherwise its time is final: record it, and push a candidate (time + edge time, neighbor) for every outgoing edge that leads to a node not yet settled.
Why a settled time is final: the heap always gives the smallest unsettled candidate. Any other route to that node has to leave the settled set through some candidate that is at least as large, and then keep adding edge times that are never negative, so it cannot arrive earlier. That is the whole proof, and it is also why one negative edge breaks the method.
The signal reaches each node at the moment its shortest path ends, so the time for everyone to hear is the largest settled time. If fewer than n nodes get settled, the rest are unreachable and the answer is -1. This is a lazy heap: instead of lowering a key in place, I push a fresh entry and ignore stale ones when they come out. Each edge pushes at most one entry, so the heap never holds more than E + 1 entries and the total cost is O(E log E). With no duplicate edges E is at most V², so that is also O(E log V). JavaScript has no built-in priority queue, so I write a small binary heap and say so.
Out loud: always lock in the cheapest arrival, then offer its neighbors a later one.
Walk it through
A dry run on the example, step by step.
| Step | Pop (time,node) | What happens | Pushed | Heap after |
|---|---|---|---|---|
| 1 | (0,1) | settle 1 at 0 | (1,2) (5,3) | (1,2) (5,3) |
| 2 | (1,2) | settle 2 at 1 | (3,3) | (3,3) (5,3) |
| 3 | (3,3) | settle 3 at 3 | (4,4) | (4,4) (5,3) |
| 4 | (4,4) | settle 4 at 4 | none | (5,3) |
| 5 | (5,3) | stale, skip | none | empty |
Take the example with k = 1. The trace shows each pop from the heap. Pop (0, 1): node 1 settles at 0, and its two edges push (1, 2) and (5, 3). Pop (1, 2): node 2 settles at 1, and its edge to node 3 pushes (3, 3), a better arrival than the (5, 3) already waiting. Pop (3, 3): node 3 settles at 3 and pushes (4, 4). Pop (4, 4): node 4 settles at 4 and has no outgoing edges.
The last pop is (5, 3), the old long route to node 3. Node 3 is already settled, so it is skipped. All four nodes are settled, the largest settled time is 4, and that is the answer. The stale entry sat in the heap the whole time and cost only one skipped pop.
The code
Runnable JavaScript, checked against test cases.
function networkDelayTime(times, n, k) {
const graph = Array.from({ length: n + 1 }, () => []);
for (const [from, to, weight] of times) graph[from].push([to, weight]);
const heap = [[0, k]];
const settled = new Array(n + 1).fill(-1);
let settledCount = 0;
let latest = 0;
while (heap.length > 0) {
const [dist, node] = popMin(heap);
if (settled[node] !== -1) continue;
settled[node] = dist;
settledCount++;
latest = Math.max(latest, dist);
for (const [next, weight] of graph[node]) {
if (settled[next] === -1) pushHeap(heap, [dist + weight, next]);
}
}
return settledCount === n ? latest : -1;
}
function pushHeap(heap, item) {
heap.push(item);
let i = heap.length - 1;
while (i > 0 && heap[(i - 1) >> 1][0] > heap[i][0]) {
const parent = (i - 1) >> 1;
[heap[parent], heap[i]] = [heap[i], heap[parent]];
i = parent;
}
}
function popMin(heap) {
const top = heap[0];
const last = heap.pop();
if (heap.length === 0) return top;
heap[0] = last;
let i = 0;
while (true) {
let smallest = i;
for (const child of [2 * i + 1, 2 * i + 2]) {
if (child < heap.length && heap[child][0] < heap[smallest][0]) smallest = child;
}
if (smallest === i) return top;
[heap[smallest], heap[i]] = [heap[i], heap[smallest]];
i = smallest;
}
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
A single node with no edges: the heap holds (0, 1), node 1 settles, the settled count equals n, and the result is 0. An unreachable node: the settled count ends below n, so the code returns -1. A source with no outgoing edges when n is above 1 gives -1 for the same reason.
Zero-time edges are fine, because the method only needs times that are not negative. Duplicate edges just add a harmless extra heap entry, and a self loop is never pushed because its node is already settled. Direction matters: an edge from A to B does not let B reach A, so the graph is stored as a directed adjacency list. The adjacency array has n + 1 slots, so labels 1 to n index it directly with no shifting.
Follow-ups to expect
Where the interviewer pushes next.
- How would you change the code to return the path to the node that hears the signal last?
- Why does a single negative edge break Dijkstra, and which algorithm handles it?
- If the graph is dense and n is small, would a plain array scan beat the heap?
- How would you answer this for many different start nodes on the same graph?
- What simpler method works if every edge takes exactly one time unit?
Where candidates slip
The mistakes this problem punishes.
Building the graph as undirected is the most common slip, because the input lists directed edges. Another is running a plain BFS and treating the number of hops as the time. BFS only works when every edge costs the same.
Others: marking a node as visited when it is pushed instead of when it is popped, which locks in a longer route before a shorter one arrives; forgetting the -1 case and returning the largest distance even when some node was never reached; starting the distance of every node at 0, which hides the unreachable ones; keeping the candidate list sorted by calling sort after every push, which turns O(E log E) into something far slower; and mixing up zero-based and one-based labels.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.