How does Dijkstra's shortest-path algorithm work?

Reported as a discussion of a shortest-path algorithm (Dijkstra) in a 2023 hiring-manager conversation, not as a timed coding prompt with a custom graph. The answer below is the standard algorithm, with a Java implementation that was compiled and run.

Problem. Given a directed or undirected graph with non-negative edge weights, a source vertex, and V vertices, compute the shortest-path distance from the source to every vertex, or report that a vertex is unreachable.

Approach. Keep a distance array, with the source at 0 and every other vertex at infinity. Repeatedly settle the unsettled vertex u with the smallest distance, then relax each outgoing edge u → v of weight w: if dist[u] + w < dist[v], update dist[v]. A binary heap (Java PriorityQueue) finds the next vertex in logarithmic time. The common lazy version inserts a new heap entry when a distance improves, and ignores stale entries when they are popped. Time is O((V + E) log V) with a binary heap. Extra space is O(V + E).

Dijkstra is wrong if any edge weight is negative; use Bellman-Ford, which allows negatives and can detect a negative cycle, at O(V E). If every edge has the same weight, a plain BFS already finds shortest paths, in O(V + E), and you should not use a heap.

import java.util.*;

public class Dijkstra {
    record Edge(int to, int weight) {}

    static int[] dijkstra(int n, List<List<Edge>> g, int src) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));
        pq.add(new int[] {src, 0});
        boolean[] done = new boolean[n];
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int u = cur[0];
            if (done[u]) continue;
            done[u] = true;
            for (Edge e : g.get(u)) {
                if (e.weight < 0) throw new IllegalArgumentException("negative weight");
                if (dist[u] != Integer.MAX_VALUE && dist[u] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[u] + e.weight;
                    pq.add(new int[] {e.to, dist[e.to]});
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        List<List<Edge>> g = new ArrayList<>();
        for (int i = 0; i < 4; i++) g.add(new ArrayList<>());
        g.get(0).add(new Edge(1, 4));
        g.get(0).add(new Edge(2, 1));
        g.get(2).add(new Edge(1, 1));
        g.get(1).add(new Edge(3, 1));
        g.get(2).add(new Edge(3, 5));
        System.out.println(Arrays.toString(dijkstra(4, g, 0))); // [0, 2, 1, 3]
    }
}

Verified with OpenJDK 21.0.13: it prints [0, 2, 1, 3]. The path 0 → 2 → 1 → 3 has length 3, which beats the direct 0 → 1 edge of weight 4 and the 0 → 2 → 3 edge of weight 6. A three-node graph with no edge into vertex 2 leaves that distance at Integer.MAX_VALUE.

Follow-ups. Reconstruct the path by storing predecessors; why a decrease-key Fibonacci heap is rarely worth it in practice; A* as Dijkstra with a heuristic; int overflow on dist[u] + w when weights are large (use long).