Priority Queues And Dijkstra's Running Time

Why the Priority Queue Matters

Dijkstra’s algorithm repeatedly chooses an unsettled vertex with the smallest tentative distance, then relaxes the outgoing arcs from that vertex. The distance-label updates are the same in each implementation; what changes is how the next minimum is found and how a decreased label is handled. That choice determines the running time.

Throughout, let \(G=(V,E)\) be a finite directed graph with nonnegative arc weights, \(n=|V|\geq 1\), and \(m=|E|\). Write \(w(u,v)\) for the weight of an arc \(uv\). Assume an adjacency-list representation, so the outgoing arcs of a vertex can be scanned in time proportional to their number. A source \(s\in V\) is given. The algorithm keeps a tentative label \(d[v]\), initially \(d[s]=0\) and \(d[v]=\infty\) for \(v\ne s\). When an unsettled vertex \(u\) is selected, each outgoing arc \(uv\) is relaxed: if \(d[u]+w(u,v)<d[v]\), set \(d[v]=d[u]+w(u,v)\).

The nonnegative-weight assumption is essential to Dijkstra’s correctness. The earlier material on the settled-vertex invariant establishes that, when the minimum tentative label is selected, that label is the true shortest-path distance. Each implementation below must therefore select a minimum current label; the data structure affects the cost of doing so, not the invariant itself.

Three Ways to Maintain the Minimum

An unsorted array keeps the unsettled vertices and their current labels, but does not keep them in key order. To extract the minimum, scan all unsettled vertices. Updating a label is constant time once its vertex is known. The array is simple, but each extraction can require a long scan.

A binary heap stores entries in a complete binary tree, represented by an array, with each parent’s key no greater than its children’s keys. The root is a minimum. Insertion and removal of the root take logarithmic time by moving an entry up or down the tree. One convenient version for Dijkstra does not implement decrease-key: every strict improvement inserts a new entry \((d[v],v)\). When an entry is removed, it is discarded if its key is no longer \(d[v]\), or if \(v\) has already been settled. This is the lazy binary-heap implementation.

An indexed priority queue stores at most one entry per vertex and maintains an index giving each vertex’s current heap position. When a label decreases, the queue changes that entry’s key and moves it up the heap as needed. This operation is called decrease-key. The position index is what distinguishes this implementation from a heap that has no direct way to locate a vertex.

Worked Traces on One Weighted Digraph

Why the Bounds Hold

Unsorted array. Initializing the \(n\) labels takes \(O(n)\) time. If the algorithm extracts a minimum for every vertex, the scans inspect \(n,n-1,\ldots,1\) unsettled labels, for \(n(n+1)/2=O(n^2)\) inspections. If it stops when the smallest remaining label is \(\infty\), it performs fewer scans, so the same upper bound holds. Each reachable vertex’s outgoing arcs are scanned at most once, contributing at most \(O(m)\). Hence the total is \(O(n^2+m)\), with \(O(n+m)\) space for labels, settled status, and adjacency lists.

Lazy binary heap. Every outgoing arc of a settled, reachable vertex is scanned at most once, so there are at most \(m\) relaxations. Only a strict improvement inserts an entry; therefore at most \(m+1\) entries are ever inserted, counting the source. A binary heap containing at most \(m+1\) entries takes \(O(\log(m+2))\) time per insertion or removal. Each inserted entry is removed once, and each arc scan takes constant time apart from a possible insertion. Initialization and bookkeeping cost \(O(n+m)\). The total is \(O(n+m+(m+1)\log(m+2))\), equivalently \(O(n+(m+1)\log(m+2))\). The heap can hold \(O(m+1)\) entries, so its additional space is \(O(m+1)\).

For a simple directed graph, \(m\leq n(n-1)\), so \(\log(m+2)=O(\log(n+1))\). Substitution gives the familiar \(O((n+m)\log(n+1))\) upper bound. Keeping the \(\log(m+2)\) expression is useful when stating the lazy-heap count directly in terms of the number of inserted entries.

Indexed priority queue. Each vertex is inserted at most once, extracted at most once, and has its key decreased at most once per successful relaxation. Thus there are at most \(n\) insertions and extractions and at most \(m\) decrease-key operations. Each heap operation costs \(O(\log(n+1))\), since the heap contains at most \(n\) vertices. Scanning adjacency lists costs \(O(m)\), so the total is \(O((n+m)\log(n+1))\). The queue, position index, labels and settled status require \(O(n)\) additional space.

Proof. Consider a removed heap entry \((k,v)\). If \(v\) is settled, the algorithm discards it and performs no relaxation. If \(v\) is unsettled and \(k\ne d[v]\), then \(k>d[v]\): the entry was created from an earlier label, and every later replacement of that label was a strict decrease. The current finite label \(d[v]\) has its own entry in the heap, inserted when that label was established. That entry has smaller key than \(k\), so the heap cannot remove \((k,v)\) as its minimum while the current entry remains. Therefore an entry that is actually used to settle a vertex has key \(d[v]\), the current minimum tentative label. The settled-vertex invariant applies to that selection, so the lazy implementation makes the same valid settlement as a queue that supports decrease-key. \(\square\)

A Common Heap Mistake

Changing a key in a binary heap is not automatically a constant-time decrease-key operation. The heap order must be restored, usually by moving the changed entry upward. For a concrete failure, let \(V=\{s,a,b,c,d\}\) and let the weighted arcs be \(E=\{(s,a,8),(s,b,1),(s,c,3),(b,a,1),(a,c,0),(c,d,1)\}\). All weights are nonnegative.

After removing \(s\), a valid heap array can have keys \([1:b,8:a,3:c]\). Removing \(b\) leaves \([3:c,8:a]\). Relaxing \(ba\) changes \(a\)'s key from \(8\) to \(2\). If the implementation changes the child’s key but does not sift it upward, the array remains \([3:c,2:a]\), which violates the heap property. It may remove \(c\) with key \(3\) before \(a\) with key \(2\). It then sets \(d[c]=3\) and \(d[d]=4\). When \(a\) is finally processed, it offers \(d[c]=2\), but \(c\) has already been settled; the algorithm can therefore return the incorrect labels \(d[c]=3,d[d]=4\).

The correction is to restore the heap order after every decrease-key, or to use the lazy strategy and insert a new \((2,a)\) entry. In the latter case the minimum is removed in the correct order, and the obsolete \((8,a)\) entry is later discarded. Dijkstra’s running time is therefore not just about the number of graph arcs: it also depends on whether the queue implements the required priority updates correctly.