Dijkstra's Algorithm

Dijkstra’s Algorithm

BFS finds shortest paths when every edge has the same weight. The moment edges carry different weights — drive times on roads, latencies between servers, costs of flight connections — BFS falls apart. Dijkstra’s algorithm fills this gap: it finds the shortest path from a single source to all other vertices in a weighted graph, as long as every edge weight is non-negative.

The Problem

Given a weighted graph $G = (V, E)$ with non-negative edge weights, find the shortest distance from a source vertex $s$ to every other vertex. Optionally, reconstruct the actual shortest path.

The Algorithm

Dijkstra’s algorithm is greedy: at every step, it finalizes the vertex with the smallest known distance, confident that no shorter path to that vertex can exist.

Steps:

1. Initialize dist[source] = 0 and dist[v] = ∞ for all other vertices.
2. Insert the source into a min-priority queue ordered by distance.
3. Extract the vertex $u$ with the smallest distance from the queue.
4. For each neighbor $v$ of $u$: if dist[u] + weight(u, v) < dist[v], relax the edge — update dist[v] and insert $v$ into the queue with its new distance.
5. Repeat until the queue is empty.

The term “relax” means: “we found a shorter path to $v$ through $u$, so update $v$‘s distance.” Edge relaxation is the fundamental operation of every shortest-path algorithm.

Java 25 Implementation

import java.util.*;

record Edge(int to, int weight) {}

record State(int node, int distance) implements Comparable<State> {
    @Override
    public int compareTo(State other) {
        return Integer.compare(this.distance, other.distance);
    }
}

record DijkstraResult(int[] dist, int[] parent) {}

DijkstraResult dijkstra(Map<Integer, List<Edge>> graph, int source, int numVertices) {
    int[] dist = new int[numVertices];
    int[] parent = new int[numVertices];
    Arrays.fill(dist, Integer.MAX_VALUE);
    Arrays.fill(parent, -1);
    dist[source] = 0;

    var pq = new PriorityQueue<State>();
    pq.add(new State(source, 0));

    while (!pq.isEmpty()) {
        var current = pq.poll();
        int u = current.node();

        // Lazy deletion: skip if we already found a shorter path
        if (current.distance() > dist[u]) continue;

        for (var edge : graph.getOrDefault(u, List.of())) {
            int v = edge.to();
            int newDist = dist[u] + edge.weight();

            if (newDist < dist[v]) {
                dist[v] = newDist;
                parent[v] = u;
                pq.add(new State(v, newDist));
            }
        }
    }

    return new DijkstraResult(dist, parent);
}

Key Implementation Details

Record types keep the code clean and self-documenting. Edge bundles a destination and weight. State bundles a node and its tentative distance, and implements Comparable so the priority queue extracts the minimum.

Lazy deletion: When we relax an edge and update dist[v], we add a new entry State(v, newDist) to the priority queue rather than updating the existing one. This means the queue can contain stale entries for the same vertex. The guard if (current.distance() > dist[u]) continue; skips these stale entries. This approach is simpler than maintaining an indexed priority queue and works well in practice.

Why Greedy Works

The correctness of Dijkstra’s algorithm rests on a single invariant: when a vertex is extracted from the priority queue, its distance is final.

Here is the intuition:

1. When we extract vertex $u$ with distance $d$, every other vertex still in the queue has distance $\geq d$ (because the queue is min-ordered).
2. Any alternative path to $u$ must pass through some vertex still in the queue, then traverse additional edges.
3. Since all edge weights are non-negative, that alternative path has total length $\geq d + 0 = d$.
4. Therefore, $d$ is already the shortest possible distance to $u$.

This argument breaks with negative edges. A path through a vertex with a larger tentative distance could become shorter after traversing a negative-weight edge. The greedy assumption — “nothing in the queue will produce a shorter path” — no longer holds.

Path Reconstruction

The parent[] array records the predecessor of each vertex on the shortest path. To reconstruct the path from source to target, backtrack through parent pointers:

List<Integer> reconstructPath(int[] parent, int target) {
    var path = new LinkedList<Integer>();
    for (int v = target; v != -1; v = parent[v]) {
        path.addFirst(v);
    }
    return path;
}

// Usage
var result = dijkstra(graph, 0, numVertices);
if (result.dist()[target] == Integer.MAX_VALUE) {
    System.out.println("No path exists");
} else {
    System.out.println("Distance: " + result.dist()[target]);
    System.out.println("Path: " + reconstructPath(result.parent(), target));
}

If dist[target] remains Integer.MAX_VALUE, no path from source to target exists in the graph.

Why Negative Edges Break Dijkstra

Consider this graph:

A --1--> B --(-5)--> C
A --3--> C

Dijkstra extracts A (dist=0), relaxes A→B (dist[B]=1) and A→C (dist[C]=3). Next it extracts B (dist=1), relaxes B→C: dist[B] + (-5) = -4 < 3. But if Dijkstra had already finalized C at distance 3, it missed the shorter path A→B→C with distance -4.

With non-negative weights, this scenario is impossible: B’s distance (1) plus any non-negative edge weight to C gives at least 1, and C was already extracted at distance 3. With non-negative edges, later relaxations cannot improve already-finalized distances.

What to use instead: For graphs with negative edges (but no negative cycles), use Bellman-Ford — it relaxes all edges V-1 times, running in O(V × E). For detecting negative cycles, Bellman-Ford runs one additional iteration: if any distance decreases, a negative cycle exists.

Optimization: Indexed Priority Queue

The standard implementation uses lazy deletion: when dist[v] is updated, a new State(v, newDist) is added to the queue. The old entry remains until it is polled and discarded. This gives time complexity O(E log E) because the queue can hold up to E entries.

An indexed priority queue (also called a decrease-key priority queue) updates the priority of an existing entry in-place:

• insert(v, dist) — add vertex with distance
• decreaseKey(v, newDist) — update vertex’s priority without duplicating
• extractMin() — remove and return the minimum

With decrease-key operations, the queue holds at most V entries, reducing the time to O(E log V) — a meaningful improvement for dense graphs where $E \gg V$.

In practice, the lazy deletion approach is preferred in interviews because:

1. Java’s PriorityQueue does not support decrease-key.
2. Implementing an indexed priority queue is complex and error-prone under time pressure.
3. For sparse graphs (typical in interviews), the difference between O(E log E) and O(E log V) is negligible.

Mention the indexed PQ as an optimization to impress your interviewer, but implement the lazy version unless explicitly asked otherwise.

Dijkstra on Grids

Many weighted-grid problems are Dijkstra problems in disguise. Each cell has a traversal cost, and you want the minimum-cost path from one corner to another.

record Cell(int row, int col, int cost) implements Comparable<Cell> {
    @Override
    public int compareTo(Cell other) {
        return Integer.compare(this.cost, other.cost);
    }
}

int minCostPath(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    dist[0][0] = grid[0][0];

    var pq = new PriorityQueue<Cell>();
    pq.add(new Cell(0, 0, grid[0][0]));

    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    while (!pq.isEmpty()) {
        var current = pq.poll();
        int r = current.row(), c = current.col();

        if (current.cost() > dist[r][c]) continue; // lazy deletion

        if (r == rows - 1 && c == cols - 1) return dist[r][c]; // early exit

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                int newCost = dist[r][c] + grid[nr][nc];
                if (newCost < dist[nr][nc]) {
                    dist[nr][nc] = newCost;
                    pq.add(new Cell(nr, nc, newCost));
                }
            }
        }
    }

    return dist[rows - 1][cols - 1];
}

Early exit: When the target cell is extracted from the priority queue, its distance is final. Return immediately — no need to process the rest of the queue.

Classic Interview Problems

Network Delay Time

Given n nodes and weighted directed edges times[i] = [u, v, w], send a signal from node k. Return the time for all nodes to receive the signal, or -1 if not all nodes are reachable.

Approach: Run Dijkstra from node k. The answer is max(dist[]). If any dist[v] remains infinity, return -1.

Cheapest Flights Within K Stops

Find the cheapest price from src to dst with at most k stops. Standard Dijkstra does not work directly because it does not track the number of stops. The fix: augment the state with a hop count.

record FlightState(int city, int cost, int stops) implements Comparable<FlightState> {
    @Override
    public int compareTo(FlightState other) {
        return Integer.compare(this.cost, other.cost);
    }
}

int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    var graph = new HashMap<Integer, List<int[]>>();
    for (int[] f : flights) {
        graph.computeIfAbsent(f[0], _ -> new ArrayList<>()).add(new int[]{f[1], f[2]});
    }

    // dist[city][stops] = min cost to reach city using exactly `stops` stops
    int[][] dist = new int[n][k + 2];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    dist[src][0] = 0;

    var pq = new PriorityQueue<FlightState>();
    pq.add(new FlightState(src, 0, 0));

    while (!pq.isEmpty()) {
        var current = pq.poll();

        if (current.city() == dst) return current.cost();
        if (current.stops() > k) continue;

        for (int[] edge : graph.getOrDefault(current.city(), List.of())) {
            int nextCity = edge[0], price = edge[1];
            int newCost = current.cost() + price;
            int newStops = current.stops() + 1;

            if (newStops <= k + 1 && newCost < dist[nextCity][newStops]) {
                dist[nextCity][newStops] = newCost;
                pq.add(new FlightState(nextCity, newCost, newStops));
            }
        }
    }
    return -1;
}

The state space expands from (vertex) to (vertex, stops), which ensures paths with different hop counts are tracked independently.

Shortest Path with Alternating Colors

Given a graph with red and blue edges, find the shortest path from node 0 to each node using paths that alternate red and blue edges. Augment the Dijkstra state with the color of the last edge used: State(node, color, distance).

Complexity Analysis

Priority Queue	Time	Space
Binary heap (lazy deletion)	O(E log E) ≈ O(E log V)	O(V + E)
Binary heap (indexed/decrease-key)	O(E log V)	O(V + E)
Fibonacci heap	O(V log V + E)	O(V + E)

• The binary heap is the standard choice. Each edge triggers at most one priority queue insertion (O(log E)), and each vertex is extracted at most once (O(log E)).
• The Fibonacci heap achieves O(V log V + E) by supporting O(1) amortized decrease-key, but its constant factors make it slower in practice for all but the largest graphs.
• Space: O(V) for the dist/parent arrays + O(E) for the adjacency list + O(E) worst case for the priority queue (lazy approach).

Algorithm Comparison

Algorithm	Problem	Edge Weights	Time	Single/All Pairs
BFS	Shortest path	Unweighted (or weight = 1)	O(V + E)	Single source
0-1 BFS	Shortest path	0 or 1	O(V + E)	Single source
Dijkstra	Shortest path	Non-negative	O(E log V)	Single source
Bellman-Ford	Shortest path	Any (detects negative cycles)	O(V × E)	Single source
Floyd-Warshall	Shortest path	Any (detects negative cycles)	O(V³)	All pairs

Decision flow:

1. All edges weight 1 (or unweighted)? → Use BFS.
2. Edges weight 0 or 1 only? → Use 0-1 BFS.
3. Non-negative weights, single source? → Use Dijkstra.
4. Negative weights possible? → Use Bellman-Ford.
5. Need all-pairs shortest paths? → Use Floyd-Warshall (small V) or run Dijkstra from every vertex (large V, non-negative weights).

Interviewer Tips

• Explain the greedy choice: “Dijkstra works because non-negative edge weights guarantee that once a vertex is extracted from the priority queue, no shorter path to it exists.” This demonstrates understanding beyond rote memorization.
• Implement the lazy version: Do not attempt an indexed priority queue under interview time pressure. The lazy approach with if (current.distance() > dist[u]) continue; is clean, correct, and expected.
• Recognize Dijkstra problems: Any “minimum cost path” in a weighted graph with non-negative edges is a Dijkstra problem. Grids with varying cell costs, flight networks with prices, network latency optimization — all Dijkstra.
• Know the negative-edge trap: If the interviewer adds a negative edge to the problem, immediately pivot: “Dijkstra assumes non-negative edges. With negative weights, I will switch to Bellman-Ford.” This shows awareness of algorithmic assumptions.
• Early termination: When you only need the distance to one specific target, mention that you can return as soon as the target is extracted from the queue. This avoids unnecessary work and impresses interviewers.
• State augmentation: For constrained shortest-path problems (at most K stops, alternating colors, fuel limits), extend the state tuple. Explain clearly what each state dimension represents and why it is necessary.