☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Why priority Queue is used in Djisktra's Algorithm

Hard TUF ID 2828 A2Z

Java source ↗ Edit this article ↗

The question

Dijkstra’s algorithm is often summarised as “BFS, but with a priority queue”. That raises fair questions. BFS with an ordinary queue already finds shortest paths in unweighted graphs, so what goes wrong with weights? Is the queue version wrong, or just slow? Would an ordered set do the same job? And is there anything the priority queue cannot fix?

This concept article answers each question with code. Every variant is a method in the accompanying Java file, they all run on the same directed graphs with edges {u, v, w}, and they all report a count of expansions: how many times some node’s edge list was scanned. main asserts on both the distances and the counts. INF marks a node that has not been reached.

static final int INF = Integer.MAX_VALUE;

record Run(int[] dist, int expansions) {}

static List<List<int[]>> buildAdj(int V, int[][] edges) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) adj.get(e[0]).add(new int[]{e[1], e[2]});
    return adj;
}

One loop, different frontiers

All the versions share one loop. Keep dist[], with dist[src] = 0 and infinity elsewhere, and a frontier of candidate pairs {distance, node}:

  1. Take a pair {d, u} out of the frontier.
  2. If d > dist[u], the pair is outdated (a better distance was found after it was added), so skip it.
  3. Otherwise expand u: for each edge u → v of weight w, if d + w < dist[v], lower dist[v] and add {dist[v], v} to the frontier.

The only design choice is which pair to take next. Notice that the loop is correct whatever that choice is, as long as there are no negative cycles. Every time dist[v] drops, a matching pair is added, and that pair is eventually expanded. So when the frontier is empty, no edge can lower any distance, and a distance array in which no edge can be improved is exactly the shortest-path array. The order affects only how much work is done.

Option 1: a plain FIFO queue

Idea. Use the BFS queue unchanged: take pairs in the order they were added.

static Run fifoQueue(int V, int[][] edges, int src) {
    List<List<int[]>> adj = buildAdj(V, edges);
    int[] dist = new int[V];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    Deque<int[]> queue = new ArrayDeque<>();
    queue.add(new int[]{0, src});
    int expansions = 0;
    while (!queue.isEmpty()) {
        int[] top = queue.poll();
        int d = top[0], u = top[1];
        if (d > dist[u]) continue;                        // outdated entry
        expansions++;
        for (int[] e : adj.get(u)) {
            if (d + e[1] < dist[e[0]]) {
                dist[e[0]] = d + e[1];
                queue.add(new int[]{dist[e[0]], e[0]});
            }
        }
    }
    return new Run(dist, expansions);
}

What goes wrong. A FIFO queue orders nodes by when they were discovered, which is roughly by number of edges from the source. With weights, few edges does not mean cheap. A node reached in two hops at cost 100 is expanded at cost 100, its neighbours are given distances based on 100, and when a five-hop route of cost 5 turns up later, the node and everything downstream of it have to be expanded again.

The Java file builds a graph that makes this happen on purpose: a row of k diamonds, where each step s_i → s_(i+1) costs 2 along one direct edge but only 1 along the two-edge detour through m_i.

static int[][] diamondChain(int k) {
    List<int[]> edges = new ArrayList<>();
    for (int i = 0; i < k; i++) {
        int s = 2 * i, m = 2 * i + 1, next = 2 * i + 2;
        edges.add(new int[]{s, next, 2});                 // short in hops, long in cost
        edges.add(new int[]{s, m, 1});
        edges.add(new int[]{m, next, 0});                 // long in hops, short in cost
    }
    return edges.toArray(new int[0][]);
}

With a FIFO queue, the direct edges (fewer hops) are always discovered before the detours (cheaper), so the distance of s_i walks down one unit at a time from 2i to its true value i, and the node is expanded once for every value on that walk, i + 1 times in total. The detour nodes behave the same way. Summed over the chain, that is exactly (k + 1)^2 expansions, which main asserts:

diamond chain k=40: FIFO expansions = 1681, heap expansions = 81

The answer is still right. The queue version is a known algorithm in its own right (Bellman-Ford with a queue, sometimes called SPFA), and its worst case is O(V × E), the same as Bellman-Ford. It is a correct algorithm with the wrong running time for this job.

Option 2: a min-heap (Java PriorityQueue)

Idea. Always take the pair with the smallest distance.

static Run priorityQueue(int V, int[][] edges, int src) {
    List<List<int[]>> adj = buildAdj(V, edges);
    int[] dist = new int[V];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.add(new int[]{0, src});
    int expansions = 0;
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int d = top[0], u = top[1];
        if (d > dist[u]) continue;                        // stale copy left behind by a later improvement
        expansions++;
        for (int[] e : adj.get(u)) {
            if (d + e[1] < dist[e[0]]) {
                dist[e[0]] = d + e[1];
                pq.add(new int[]{dist[e[0]], e[0]});
            }
        }
    }
    return new Run(dist, expansions);
}

Why that fixes the work. With non-negative weights, the smallest pair {d, u} in the frontier is final: d is the true shortest distance of u. Any other route to u must pass through some pair still in the frontier, whose distance is already at least d, and the remaining edges of that route can only add non-negative amounts. So nothing can ever improve dist[u] after this pop, and u is expanded exactly once. On the diamond chain that is 2k + 1 = 81 expansions, and main asserts the once-per-node rule on every test graph.

Lazy deletion. Java’s PriorityQueue cannot lower the key of an element already inside it. Instead of updating the old pair {12, v} when dist[v] drops to 9, we simply add {9, v}. The old pair stays in the heap and is skipped by the d > dist[u] check when it eventually surfaces. Stale pairs are harmless: they cost one poll each and are never expanded.

Complexity. Each node is expanded once, so each edge is relaxed once and at most E + 1 pairs are ever pushed. Every push and pop is O(log E), and log E ≤ 2 log V, so the total is O((V + E) log V). Compare that with the FIFO queue’s O(V × E) worst case.

Option 3: an ordered set (TreeSet)

Idea. Get a real decrease-key instead of lazy deletion. Keep the frontier in a TreeSet ordered by (distance, node). When dist[v] improves, remove the old pair {dist[v], v} and insert the new one.

static Run treeSet(int V, int[][] edges, int src) {
    List<List<int[]>> adj = buildAdj(V, edges);
    int[] dist = new int[V];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    TreeSet<int[]> set = new TreeSet<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
    set.add(new int[]{0, src});
    int expansions = 0;
    while (!set.isEmpty()) {
        int[] top = set.pollFirst();
        int d = top[0], u = top[1];
        expansions++;                                     // never stale: the set holds one entry per node
        for (int[] e : adj.get(u)) {
            int v = e[0], nd = d + e[1];
            if (nd < dist[v]) {
                if (dist[v] != INF) set.remove(new int[]{dist[v], v});
                dist[v] = nd;
                set.add(new int[]{nd, v});
            }
        }
    }
    return new Run(dist, expansions);
}

The set holds at most one pair per node, so it never grows beyond V and nothing is ever stale. pollFirst() returns the smallest pair, exactly like the heap, so each node is again expanded once and the time is O((V + E) log V).

Two details matter in Java:

In practice the heap is usually faster in Java (an array instead of a tree of nodes), while the set keeps memory bounded by V when distances improve many times. For dense graphs, an array scan for the minimum, O(V^2 + E), beats both; it appears in the Dijkstra’s Algorithm article.

What the priority queue cannot fix: negative edges

The “smallest pair is final” argument used one assumption: the rest of a route cannot make it cheaper. A negative edge breaks exactly that. The textbook version of Dijkstra makes the assumption explicit by freezing a node the moment it is popped:

static int[] settleOnPop(int V, int[][] edges, int src) {
    List<List<int[]>> adj = buildAdj(V, edges);
    int[] dist = new int[V];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    boolean[] settled = new boolean[V];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.add(new int[]{0, src});
    while (!pq.isEmpty()) {
        int u = pq.poll()[1];
        if (settled[u]) continue;
        settled[u] = true;                                // dist[u] is declared final here
        for (int[] e : adj.get(u)) {
            int v = e[0];
            if (!settled[v] && dist[u] + e[1] < dist[v]) {
                dist[v] = dist[u] + e[1];
                pq.add(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

On the graph 0→1 (2), 0→2 (5), 2→1 (-4) it pops node 1 at distance 2 and freezes it. When node 2 is expanded later, the cheaper route 0 → 2 → 1 of cost 1 is ignored. The reference answer comes from Bellman-Ford, which relaxes every edge V - 1 times and does not depend on any order:

static int[] bellmanFord(int V, int[][] edges, int src) {
    int[] dist = new int[V];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int round = 1; round < V; round++) {
        for (int[] e : edges) {
            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2];
        }
    }
    return dist;
}
method dist on the negative-edge graph
settleOnPop [0, 2, 5] (wrong for node 1)
bellmanFord [0, 1, 5]
priorityQueue (lazy) [0, 1, 5], but with 4 expansions for 3 nodes

The lazy heap version recovers here only because it never freezes anything: node 1 is pushed again with distance 1 and expanded a second time. That is precisely the once-per-node guarantee disappearing, and on adversarial graphs with negative edges this kind of re-expansion can take exponential time. With negative weights, use Bellman-Ford, or a topological-order sweep if the graph is a DAG.

Summary

frontier next node taken expansions per node time
FIFO queue oldest discovered possibly many O(V × E) worst case
min-heap with lazy deletion smallest distance exactly one O((V + E) log V)
TreeSet with remove-then-add smallest distance exactly one O((V + E) log V)

The priority queue is not what makes Dijkstra correct; the relax-until-nothing-improves loop is correct with any frontier. The priority queue is what makes it efficient: by always expanding the closest unfinished node, it guarantees that the first expansion of each node is its last. That guarantee, and therefore the whole speed-up, depends on the weights being non-negative.