Dijkstra's Shortest Path Algorithm

Dijkstra's Shortest Path Algorithm

Dijkstra's algorithm finds shortest paths from one source vertex to every other vertex in a weighted graph by repeatedly pulling the closest not-yet-finalized vertex off a min-heap and using its now-final distance to relax (tighten) its neighbors' distances. Because every edge weight is non-negative, once a vertex is popped from the heap its recorded distance can never be beaten later by some other path through a farther vertex — so that pop is safe to treat as final. It is the same greedy-frontier idea as BFS, generalized from "one hop = one step" to "one hop = arbitrary non-negative cost," with a priority queue replacing the plain FIFO queue so the frontier always expands in true accumulated-cost order rather than arrival order.

Recognize the pattern

• The problem asks for the shortest / cheapest / minimum-cost path from a single source, on a graph with weighted edges.
• All edge weights are guaranteed to be ≥ 0 (distance, time, price, capacity-cost — never a "refund" or a negative adjustment).
• You need distances to every reachable node, not just one target (for a single target, Dijkstra with early-exit on pop of that node still applies and is often faster in practice).
• Phrases like "cheapest flight route," "minimum toll cost to reach," "shortest travel time on a road network" are the classic tells.
• If all weights are equal, this collapses to BFS with a plain queue — reach for Dijkstra only once weights genuinely differ.

Brute force baseline → Dijkstra

Naive baseline (Bellman-Ford style): relax every edge in the graph, repeat that pass |V|−1 times, until no distance improves. This is correct even with negative edges (so long as there is no negative cycle), but it costs O(V·E) because it keeps re-examining edges out of vertices whose shortest distance is already known and settled.

Dijkstra's improvement: exploit non-negativity. Once you pop the minimum-distance vertex from a priority queue, no unexplored edge can ever produce a shorter path to it (all remaining candidate paths pass through vertices that are at least as far away, and adding a non-negative edge cannot make them shorter). So each vertex needs to be finalized exactly once, and each edge needs to be relaxed exactly once, for a total cost of O((V+E) log V) instead of O(V·E). The trade is a bookkeeping structure (the heap) in exchange for never redoing settled work.

Complexity, derived from first principles

Time. Every vertex is popped from the heap; with a lazy-deletion heap (the standard interview-friendly implementation, no decrease-key), every relaxation that improves a distance pushes a fresh (distance, vertex) pair rather than mutating an existing heap entry. Each of the E edges can trigger at most one push, so the heap holds at most O(E) entries over the algorithm's lifetime (plus the O(V) initial pushes). Each push/pop on a heap of size O(E) costs O(log E); since E ≤ V², log E = O(log V). Total: O(V) pops for the outer loop skeleton plus O(E) pushes/pops for relaxations, each O(log V) → O((V+E) log V). (A decrease-key-capable heap, e.g. a Fibonacci heap, tightens this to O(E + V log V), but is rarely worth the implementation cost in interviews.)

Space. O(V) for the distance array and the finalized/visited array, plus O(E) for the adjacency list and O(E) for the heap in the worst case (one stale entry per relaxation) → O(V + E).

Worked example

Directed graph, source A. Edges: A→B(4), A→C(1), C→B(2), B→D(5), C→D(8), C→E(10), D→E(2).

Final shortest distances from A: A=0, C=1, B=3, D=8, E=10. Two heap entries (4,B) and (9,D) were pushed before a cheaper route was discovered, then popped and thrown away later — that is lazy deletion in action.

Reference implementation (Java)

import java.util.*;

public final class Dijkstra {
    // adj[u] = list of {v, weight} edges out of u
    public static int[] shortestPaths(int n, List<int[]>[] adj, int src) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        boolean[] done = new boolean[n];
        // min-heap ordered by tentative distance; lazy deletion means we
        // push a fresh entry on every improvement instead of mutating one
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.offer(new long[]{0L, src});

        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            int d = (int) top[0];
            int u = (int) top[1];
            if (done[u]) continue;      // stale heap entry: a shorter path
            done[u] = true;             // already finalized this vertex
            for (int[] edge : adj[u]) {
                int v = edge[0], w = edge[1];
                if (!done[v] && dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }
        return dist; // Integer.MAX_VALUE entries mean unreachable
    }
}

Pitfalls

• Negative edge weights break the core invariant. The whole algorithm rests on "once popped, a vertex's distance is final because every unexplored path is at least as long." A negative edge can let a longer-looking path suddenly become shorter after a vertex was already finalized and closed off — Dijkstra will never revisit it, producing a wrong (too large) answer silently, with no crash to warn you.
• Negative cycles make "shortest path" undefined (you can loop forever, decreasing cost each time); no comparison-based single-source algorithm can return a finite answer, and Dijkstra especially will not detect the problem.
• Forgetting the stale-entry check (`if (done[u]) continue;`) causes vertices to be re-processed multiple times, re-relaxing already-final edges — this doesn't corrupt correctness but silently degrades a supposedly O((V+E) log V) run to something far slower and confuses complexity analysis.
• Overflow / reachability: summing into Integer.MAX_VALUE without a reachability guard overflows to a negative number and creates phantom "shorter" paths through unreachable vertices — always guard with dist[u] != INF before adding.

When to use / when NOT — trade-offs

Takeaways

• Dijkstra is BFS generalized to non-negative weights: a priority queue replaces the FIFO queue so the frontier expands in true cost order.
• Correctness depends entirely on non-negative edges — that single assumption is what makes "pop = final" safe; violate it and reach for Bellman-Ford instead.
• Lazy deletion (push-on-improve, skip-if-already-done on pop) is the practical, interview-standard way to simulate decrease-key with a plain binary heap, at the cost of a few extra stale entries.
• Complexity is derived, not memorized: O(V) finalizations + O(E) relaxations, each heap operation O(log V), plus O(V+E) space for the adjacency list, distance array, and heap.
• If weights are all equal, drop back to plain BFS; if edges can be negative (but no negative cycle), move up to Bellman-Ford; if you need all-pairs, prefer Floyd-Warshall or Johnson's over calling Dijkstra V times naively on negative weights.

Recall question: Why does Dijkstra fail on a graph with a negative edge weight even though it uses a priority queue exactly the way BFS uses a plain queue — what specific guarantee does popping the minimum lose?

Authored for this guide; concepts and complexity analysis follow the standard treatment in CLRS (Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms") Ch. 24, and Sedgewick & Wayne, "Algorithms."