Dijkstra Visualization for Coding Interviews
Min-heap relax; fails on negative edges — demo included.
Concept
Dijkstra's algorithm is the default answer for single-source shortest paths on a graph with non-negative edge weights. It generalizes BFS: instead of exploring vertices in hop order, it explores them in cost order, greedily pulling the cheapest unfinalized vertex off a min-heap and relaxing its outgoing edges. The invariant that makes the greed safe is exactly the constraint people forget - edge weights must be non-negative. Once that holds, the first time a vertex is popped from the heap its distance is final, because any later path through any unprocessed vertex could only add non-negative cost. Real-world uses are everywhere: routing, map directions, network protocols like OSPF, weighted state-space search, and almost any "cheapest path" problem you run into in systems. With a binary heap and an adjacency list, Dijkstra runs in O((V+E) log V); with a Fibonacci heap it drops to O(E + V log V), though in practice a PriorityQueue<int[]> is what everyone ships.
How it works
Initialize dist[src] = 0 and every other distance to a large sentinel. Push (0, src) into a min-heap ordered by tentative distance. Pop the smallest (d, u); if d is stale (greater than the currently recorded dist[u]), discard and keep popping - this lazy-deletion trick is why we tolerate duplicate heap entries and avoid a decrease-key operation. Otherwise, iterate u's neighbors. For each edge (u, v, w), compute nd = dist[u] + w; if nd < dist[v], update dist[v] = nd, record parent[v] = u, and push (nd, v). Continue until the heap empties or you pop the target. Two design choices matter. First, the lazy-deletion pattern: when you find a cheaper path to v, you leave the old entry in the heap and just push a new one; the stale one is discarded on pop. Second, the non-negative weight requirement: with a negative edge, a vertex already finalized could later be improved by relaxing a negative edge backwards into it, and the greedy pop-once-is-final invariant breaks. For negative weights, switch to Bellman-Ford; for a DAG, use topological order and linear relaxation instead.
Implementation
import java.util.*;
public class Dijkstra {
/**
* Single-source shortest paths on a non-negative weighted graph.
* edges[i] = {u, v, w} representing a directed edge u -> v of weight w.
* Returns dist[v] = shortest cost from src to v, or Long.MAX_VALUE if unreachable.
*
* Note: Dijkstra is incorrect on graphs with negative edges because once a vertex
* is popped from the heap it is treated as finalized; a later negative relaxation
* can never be applied. Use Bellman-Ford when negative weights are possible.
*/
public static long[] dijkstra(int[][] edges, int src, int n) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) adj.get(e[0]).add(new int[] { e[1], e[2] });
long[] dist = new long[n];
Arrays.fill(dist, Long.MAX_VALUE);
dist[src] = 0L;
// Min-heap keyed by tentative distance. int[] = {vertex, dist}.
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
pq.offer(new long[] { src, 0L });
while (!pq.isEmpty()) {
long[] top = pq.poll();
int u = (int) top[0];
long d = top[1];
if (d > dist[u]) continue; // stale lazy-deleted entry
for (int[] nxt : adj.get(u)) {
int v = nxt[0];
int w = nxt[1];
long nd = d + w;
if (nd < dist[v]) {
dist[v] = nd;
pq.offer(new long[] { v, nd }); // push; do not decrease-key
}
}
}
return dist;
}
}Complexity
- Time:
O((V + E) log V) - Space:
O(V + E)
Common pitfalls
- Running Dijkstra on a graph with any negative edge - the first-pop-is-final invariant breaks and results are silently wrong.
- Storing distances as int and overflowing when edge weights sum past Integer.MAX_VALUE; use long for the accumulator.
- Skipping the stale-entry check (d > dist[u]) and re-relaxing vertices, which turns the algorithm quadratic.
- Trying to implement a decrease-key on Java's PriorityQueue - it does not support it; push a duplicate and filter on pop.
- Forgetting that the heap may hold O(E) entries over the run, not just O(V), because we push on every successful relaxation.
Key design decisions & trade-offs
- Heap strategy — Chosen: Lazy deletion with duplicate entries. Avoids the complexity of a decrease-key-capable heap; the asymptotic factor is unchanged and the code is much shorter.
- Adjacency representation — Chosen: List<List<int[]>> from an edge list. Linear conversion cost, O(1) amortized neighbor iteration, and no O(V^2) matrix allocation for sparse graphs.
- Dijkstra vs Bellman-Ford — Chosen: Dijkstra for non-negative weights. Dijkstra is O((V+E) log V) vs Bellman-Ford's O(V*E); only pay the BF cost when negatives are truly possible.
Practice problems
Interview follow-ups
- A* search: Dijkstra plus a consistent heuristic to prune the frontier.
- Bidirectional Dijkstra to cut work roughly in half for point-to-point queries.
- Johnson's algorithm: use Bellman-Ford to reweight, then run Dijkstra from every source for all-pairs.
- Dial's algorithm (bucket queue) when weights are small integers.
- K-shortest paths with Yen's algorithm layered on top of Dijkstra.
Why it matters
Dijkstra is a core part of the Graphs toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".