Dijkstra's Algorithm — Fixing Cyclic Graph Heap Explosion

Every time Google Maps reroutes you around traffic, every time a network router decides which packet path costs the least, and every time an airline computes the cheapest connecting flights, Dijkstra's algorithm — or something built directly on top of it — is doing the heavy lifting. It was published by Edsger W. Dijkstra in 1959, and it remains one of the most practically deployed algorithms in computer science history. That kind of longevity isn't accidental.

The core problem Dijkstra solves is this: given a weighted graph where edge weights are non-negative, find the minimum-cost path from a single source vertex to every other reachable vertex. A naive approach — trying every possible path — explodes combinatorially. Dijkstra's insight was that you can build the solution greedily: if you always expand the unvisited vertex with the currently known lowest cost, you're guaranteed never to find a cheaper path to it later (provided weights are non-negative). That greedy guarantee is the algorithm's heartbeat.

By the end of this article you'll understand not just how to implement Dijkstra with a priority queue in Java, but why the min-heap is mandatory for the efficient version, what happens internally when you relax an edge, why negative weights break the algorithm at a fundamental level (not just practically), how to handle common production gotchas like disconnected graphs and duplicate heap entries, and exactly how to answer the curveball Dijkstra questions interviewers love to throw.

What is Dijkstra's Algorithm? — Plain English

Dijkstra's algorithm finds the shortest path from one source node to all other nodes in a weighted graph where all edge weights are non-negative. Think of a GPS: your phone knows the travel time on every road and wants the fastest route. It never backtracks to a road it already 'settled' because it always picks the closest unsettled destination next — and since weights are non-negative, no future road could make a settled destination cheaper.

The key insight is greedy correctness: if you always expand the node with the current minimum distance, the first time you reach a node is guaranteed to be the shortest path. This breaks down with negative weights because a future negative edge could provide a cheaper route to an already-settled node.

How Dijkstra's Algorithm Works — Step by Step

Dijkstra uses a min-heap (priority queue) to always process the nearest unsettled node next.

1. Initialize dist[source] = 0, dist[all others] = infinity.
2. Push (0, source) into the min-heap.
3. While the heap is non-empty:
4. a. Pop the node u with the smallest current distance d.
5. b. If d > dist[u], skip — this is a stale entry (we already found a shorter path to u).
6. c. For each neighbour v of u with edge weight w:
7. - If dist[u] + w < dist[v], update dist[v] = dist[u] + w and push (dist[v], v) to the heap.
8. After the heap is empty, dist[v] holds the shortest distance from source to every reachable node v.

Time complexity: O((V + E) log V) with a binary min-heap. Space: O(V) for distances and the heap.

Worked Example — Tracing the Algorithm

Graph (5 nodes 0-4, directed weighted edges): 0->1 w=2, 0->2 w=4, 1->2 w=1, 1->3 w=7, 2->4 w=3, 3->4 w=1

Start: dist=[0, INF, INF, INF, INF]. Heap: [(0,0)]

Iteration 1: pop (0,0). Process node 0. Edge 0->1 w=2: dist[1] = min(INF, 0+2) = 2. Push (2,1). Edge 0->2 w=4: dist[2] = min(INF, 0+4) = 4. Push (4,2). dist=[0,2,4,INF,INF]. Heap: [(2,1),(4,2)]

Iteration 2: pop (2,1). Process node 1. Edge 1->2 w=1: dist[2] = min(4, 2+1) = 3. Push (3,2). Edge 1->3 w=7: dist[3] = min(INF, 2+7) = 9. Push (9,3). dist=[0,2,3,9,INF]. Heap: [(3,2),(4,2),(9,3)]

Iteration 3: pop (3,2). Process node 2. Edge 2->4 w=3: dist[4] = min(INF, 3+3) = 6. Push (6,4). dist=[0,2,3,9,6]. Heap: [(4,2),(6,4),(9,3)]

Iteration 4: pop (4,2). d=4 > dist[2]=3, stale entry. Skip.

Iteration 5: pop (6,4). Process node 4. No outgoing edges.

Iteration 6: pop (9,3). Process node 3. Edge 3->4 w=1: dist[4] = min(6, 9+1) = 6. No improvement.

Final distances from node 0: [0, 2, 3, 9, 6]

Java Implementation — Min-Heap, Stale Entry Handling, and Edge Cases

Below is a production-grade Java implementation of Dijkstra using java.util.PriorityQueue with a custom comparator. It includes the mandatory stale entry check, returns both distances and predecessor map for path reconstruction, and handles disconnected graphs gracefully.

package io.thecodeforge.graph;

import java.util.*;

public class Dijkstra {
    public static class Result {
        public final Map<Integer, Integer> distance;
        public final Map<Integer, Integer> predecessor;

        public Result(Map<Integer, Integer> distance, Map<Integer, Integer> predecessor) {
            this.distance = distance;
            this.predecessor = predecessor;
        }
    }

    public static Result shortestPath(Map<Integer, List<int[]>> graph, int source) {
        Map<Integer, Integer> dist = new HashMap<>();
        Map<Integer, Integer> pred = new HashMap<>();
        for (int node : graph.keySet()) {
            dist.put(node, Integer.MAX_VALUE);
        }
        dist.put(source, 0);

        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        heap.offer(new int[]{source, 0});

        while (!heap.isEmpty()) {
            int[] current = heap.poll();
            int u = current[0];
            int d = current[1];

            if (d > dist.get(u)) continue; // stale entry

            List<int[]> neighbors = graph.get(u);
            if (neighbors == null) continue;

            for (int[] edge : neighbors) {
                int v = edge[0];
                int w = edge[1];
                int newDist = dist.get(u) + w;
                if (newDist < dist.get(v)) {
                    dist.put(v, newDist);
                    pred.put(v, u);
                    heap.offer(new int[]{v, newDist});
                }
            }
        }

        return new Result(dist, pred);
    }

    public static void main(String[] args) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(new int[]{1,2}, new int[]{2,4}));
        graph.put(1, Arrays.asList(new int[]{2,1}, new int[]{3,7}));
        graph.put(2, Arrays.asList(new int[]{4,3}));
        graph.put(3, Arrays.asList(new int[]{4,1}));
        graph.put(4, Collections.emptyList());

        Result r = shortestPath(graph, 0);
        System.out.println("Distances: " + r.distance);
        System.out.println("Predecessors: " + r.predecessor);
    }
}

Edge Cases and Production Pitfalls

Dijkstra seems simple but production code fails in subtle ways. Here are the common edge cases: - Disconnected graph: Nodes unreachable from source remain at INF. Always check for INF before using the distance. - Self-loops and zero-weight cycles: Dijkstra can handle zero-weight edges, but a zero-weight cycle may cause infinite loop if you don't skip stale entries. The stale entry check prevents this. - Parallel edges: Multiple edges between same nodes. Dijkstra correctly picks the smallest weight due to the relaxation step. - Integer overflow: Sum of weights can exceed Integer.MAX_VALUE. Use long for distances. - Multiple sources: For multi-source shortest paths, initialize all sources with dist=0 and push all of them into heap. Works identically. - Large graphs: For graphs with millions of nodes, use adjacency list not adjacency matrix. Consider bidirectional search if you only need a single pair. - Negative weights: Dijkstra gives wrong answers. Validate input and throw exception if any negative weight found.

Frequently Asked Questions