Dijkstra's Algorithm in Java — Shortest Path with PriorityQueue

Dijkstra's algorithm — what it does

• Single-source shortest path
• Weighted graph
• Non-negative weights (critical limitation)

Algorithm

1. Initialize

• All distances = infinity
• dist[source] = 0
• Push (0, source) onto min-heap

2. Loop

• Pop (d, u) — the smallest distance
• If d > dist[u]: stale entry, skip
• Else: relax all outgoing edges

  • For each (v, weight): if d + weight < dist[v], update and push

3. Continue until heap empty

Greedy invariant

• At each step, finalize the closest unvisited vertex
• Once finalized, distance is correct
• No future relaxation can improve it
• Why non-negative weights matter: negative would invalidate this

Java implementation

int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;

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

while (!pq.isEmpty()) {
    int[] cur = pq.poll();
    int d = cur[0], u = cur[1];
    if (d > dist[u]) continue;   // lazy deletion
    for (int[] edge : adj.get(u)) {
        int v = edge[0], w = edge[1];
        int newDist = d + w;
        if (newDist < dist[v]) {
            dist[v] = newDist;
            pq.offer(new int[]{newDist, v});
        }
    }
}

Complexity

With binary heap (Java's PQ) + adjacency list

• O((V + E) log V)
• Standard implementation

With array + matrix

• O(V²)
• Better for dense graphs

With Fibonacci heap

• O(E + V log V)
• Theoretical; rarely implemented

Lazy deletion explained

Problem

• Java's PriorityQueue has no efficient decrease-key
• Removing arbitrary element is O(n)

Solution

• Just push duplicate entries when you find a shorter path
• When popping, check if d > dist[u]; if so, skip
• Stale entries are 'lazily deleted' by being ignored

Correctness

• Heap pops smallest first
• First time we pop (d, u) with d == dist[u]: that's the final answer
• Later pops with same u have d ≥ dist[u]: stale, skip

Total complexity

• O(E) pushes total (one per edge in worst case)
• O(log V) per operation
• O((V + E) log V)

Limitations

1. Negative weights

• Dijkstra fails
• Greedy choice invalid
• Use Bellman-Ford (O(V · E))

2. Negative cycle

• No shortest path (loop forever)
• Bellman-Ford detects this

3. Very large graphs

• Use bidirectional Dijkstra, A*, contraction hierarchies

4. Frequent graph updates

• Recompute is expensive
• Static graphs are the sweet spot

Variants

A*

• Dijkstra + heuristic
• f(v) = g(v) + h(v)
• Faster for known target
• Manhattan / Euclidean distance heuristics
• Used in games, GPS

Bidirectional Dijkstra

• Forward from source + backward from target
• Meet in middle
• ~2× faster
• Useful for huge graphs

0-1 BFS

• Special case: weights only 0 or 1
• Use deque
• Push 0-weight to front, 1-weight to back
• O(V + E)

Multi-source Dijkstra

• Init all sources with distance 0
• Push all to heap
• 'Closest of any source' problems

Contraction hierarchies (real world)

• Preprocess: rank vertices, add shortcut edges
• Query: 1000× faster
• Used by Google Maps, OSRM, Graphhopper
• Continental road networks: sub-millisecond queries

Path reconstruction

int[] parent = new int[n];
Arrays.fill(parent, -1);
// In relaxation:
parent[v] = u;
// Reconstruct:
List<Integer> path = new ArrayList<>();
for (int c = target; c != -1; c = parent[c]) path.add(c);
Collections.reverse(path);

Common bugs

1. Not handling stale entries

• Without lazy deletion check: wastes work, but still correct
• With check: optimal

2. Using on negative weights

• Wrong answer
• Use Bellman-Ford

3. Integer overflow

• d + weight can overflow if d == MAX_VALUE
• Check dist[u] != MAX_VALUE first
• Or use long

4. Forgetting bidirectional add for undirected

• Add to both u's and v's adjacency lists

5. Wrong PQ ordering

• Must be MIN-heap
• Default Java PQ is min-heap when using natural order
• Comparator: comparingInt(a -> a[0])

6. Using LinkedList or Stack

• LinkedList: no priority semantics
• Stack: LIFO, not min
• Use PriorityQueue (binary heap) or TreeSet

Compared to other algorithms

BFS

• Unweighted shortest path
• O(V + E)
• Dijkstra reduces to BFS when all weights = 1

Bellman-Ford

• Negative weights OK
• O(V · E)
• Detects negative cycles
• Used in RIP routing protocol

Floyd-Warshall

• All-pairs shortest path
• O(V³)
• Works for any weights without negative cycles
• Small V only

A*

• Dijkstra + heuristic
• Optimal if heuristic admissible
• Faster for known target

For interviews

• Implement Dijkstra cold
• Use PriorityQueue + lazy deletion
• Mention O((V + E) log V)
• Address no-negative-weights limitation
• Mention Bellman-Ford for negatives, A* for known target, bidirectional for huge graphs

Recommendation: Implement Dijkstra's algorithm in Java using `PriorityQueue` keyed by distance and an adjacency list — this gives you O((V + E) log V) time, which is the standard for sparse graphs. Use the lazy deletion pattern (skip with if (d > dist[u]) continue;) because Java's PriorityQueue doesn't support efficient decrease-key; just push duplicate entries when you find shorter paths and ignore stale ones when popping. Initialize distances to `Integer.MAX_VALUE` and source to 0; avoid integer overflow by checking dist[u] != MAX_VALUE before adding weight, or use long. The critical limitation: Dijkstra does not work with negative edge weights — the greedy 'finalize closest' invariant breaks. For negative weights, use Bellman-Ford (O(V · E), detects negative cycles); for DAGs use topological sort + relaxation (O(V + E)); for all-pairs use Floyd-Warshall (O(V³)) or Johnson's (O(V · E log V)); for graphs with weights only 0 or 1, 0-1 BFS with a deque achieves O(V + E). For known-target search, use A* with an admissible heuristic (Manhattan, Euclidean) for big speedups. For huge static graphs (continental road networks), use contraction hierarchies — preprocess once, query in sub-millisecond (used by Google Maps, OSRM, Graphhopper). For path reconstruction, maintain a parent[] array and trace backward from target. The mental model: Dijkstra = greedy expansion from cheapest frontier; valid because finalizing the closest vertex is always safe with non-negative weights. For interviews, implement it cold, mention the lazy deletion trick, the negative-weight limitation, and gracefully transition to *Bellman-Ford / A* / contraction hierarchies* when asked about variants.