DSA · Patterns, not puzzles
How does Dijkstra's algorithm work?
Short answer
Dijkstra repeatedly extracts the unvisited node with the smallest known distance and relaxes its outgoing edges. With a binary heap it runs in O((V + E) log V) and requires non-negative edge weights.
The algorithm grows a set of nodes whose shortest distance is finalized. A priority queue always gives the closest frontier node. Because all edge weights are non-negative, no later path can improve a finalized distance, which is why the greedy choice is safe.
class MinHeap {
constructor() {
this.data = [];
}
push(item) {
this.data.push(item);
let index = this.data.length - 1;
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
if (this.data[parent][0] <= this.data[index][0]) break;
[this.data[parent], this.data[index]] = [
this.data[index],
this.data[parent],
];
index = parent;
}
}
pop() {
const top = this.data[0];
const last = this.data.pop();
if (this.data.length > 0) {
this.data[0] = last;
let index = 0;
while (true) {
const left = index * 2 + 1;
const right = index * 2 + 2;
let smallest = index;
if (left < this.data.length && this.data[left][0] < this.data[smallest][0]) {
smallest = left;
}
if (right < this.data.length && this.data[right][0] < this.data[smallest][0]) {
smallest = right;
}
if (smallest === index) break;
[this.data[index], this.data[smallest]] = [
this.data[smallest],
this.data[index],
];
index = smallest;
}
}
return top;
}
}
function dijkstra(graph, start) {
const distances = new Map();
for (const node of graph.keys()) distances.set(node, Infinity);
distances.set(start, 0);
const heap = new MinHeap();
heap.push([0, start]);
while (heap.data.length > 0) {
const [distance, node] = heap.pop();
if (distance > distances.get(node)) continue;
for (const [next, weight] of graph.get(node) || []) {
const candidate = distance + weight;
if (candidate < distances.get(next)) {
distances.set(next, candidate);
heap.push([candidate, next]);
}
}
}
return distances;
}Why the assumptions matter
- Negative edges break the greedy finalisation guarantee
- Use Bellman-Ford when negative edges may be present
- A binary heap gives O((V + E) log V)
- A simple array scan gives O(V^2), which is fine for dense graphs
- Dijkstra finds single-source shortest paths, not all-pairs
For unweighted graphs, BFS is simpler and faster. For dense graphs with a small vertex count, the O(V^2) array implementation can outperform a heap because it avoids heap overhead and supports O(1) edge lookup with a matrix.
Follow-ups you should expect
Interviewers use these to check whether the first answer was understanding or memorisation.
- 1Why can't Dijkstra handle negative edge weights?
- 2What is the complexity with a binary heap?
- 3When would you use Bellman-Ford instead?
- 4How do you reconstruct the shortest path?
Say it in the interview
Dijkstra keeps a priority queue of the closest known nodes, pops the smallest distance, and relaxes its outgoing edges. Because edge weights are non-negative, the first time I finalize a node its distance is optimal. With a binary heap the complexity is O((V + E) log V), and if negative edges are possible I use Bellman-Ford instead.
Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.
Related questions
Reading is step one
Now say it out loud.
Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.