Simpler Universally Optimal Dijkstra

We offer a significantly more concise proof of Dijkstra’s universal optimality. Our main insight is to replace the working-set bound with a conceptually simpler measure called timestamps.¹¹1We note that the original work by Iacono [10] included several notions of working-set bounds. One of these notions, not present in [6, 9], but used in [5], matches our notion of timestamp optimality. By working set, we explicitly refer to the definition used in [6, 9]. We use the more distinct term timestamps to properly distinguish between the concepts in this work and [6]. This also highlights that our notion yields a family of intervals $[a_i,b_i]$, which is more convenient than having just the working set sizes $\varphi (x_i)$. We maintain a heap $H$ and global time counter that increments after $H$.Push. For each heap element $x_i$, let $a_i$ and $b_i$ denote the time it was pushed and popped, respectively. We define $H$ to be timestamp optimal if popping $x_i$ takes $O(1+\log (b_i-a_i))$ time. Timestamps are not only conceptually simpler than working-set sizes, timestamp optimality is also considerably simpler to implement.

We design a heap data structure that supports Push and DecreaseKey in amortized constant time, and Pop in amortized $O(1+\log (b_i-a_i))$ time. Using timestamps, we show a universal lower bound of $\mathrm{\Omega }(m+{\sum }_{x_i\in V\setminus \{s\}}(1+\log (b_i-a_i)))$ for any fixed graph topology $G=(V,E)$ and source $s$. We consider this to be our main contribution, as it offers a significantly simpler proof that Dijkstra’s algorithm can be made universally optimal. Finally, our formulation of timestamps allow us to apply recent techniques for universally optimal sorting [5, 11] to show that Dijkstra’s algorithm, with our timestamp optimal heap, matches our universal lower bound. Additionally, we show in the full version that our algorithm is equally general to that of [6], as it can be made universally optimal with respect to edge weight comparisons. While this proof is indeed new, different, and perhaps simpler, it is not self-contained; therefore, we relegate it to the full version for the sake of completeness.

Let $H$ denote our abstract heap data structure, supporting operations $H.\text{Push}(x,y)$, $H.\text{DecreaseKey}(x,y)$, and $H.\text{Pop}()$. We implement $H$ as follows:

By Invariant 1, for all elements $x_i\in B[j]$, $(t-a_i)$ is at least $2^{j-1}$, but less than $2^{j+2}$. We define $M$ as an array of size $\lceil \log n\rceil$, where $M[j]$ stores the minimum key in $B[j]$. Furthermore, we maintain a bitstring $S_M$ where $S_M[j]=1$ if for all $k>j$, we have $M[j]\le M[k]$.

Let $a_i$ be the insertion time of $x_i$. We now want to determine the possible values $j$ such that $B[j]$ contains $x_i$. From invariant 1.b we get: $t-a_i\ge 2^{j-1}$, or equivalently, $j\le \log (t-a_i)+1$; and , or equivalently, $j>\log (t-a_i)-2$. In particular, for $\mathrm{\ell }=\lfloor \log (t-a_i)\rfloor$, the Fibonacci heap containing $x_i$ lies in one of the buckets $B[\mathrm{\ell }-1],B[\mathrm{\ell }],B[\mathrm{\ell }+1]$. For each of these at most $6$ corresponding intervals of the at most $6$ heaps contained in those $3$ buckets, we test, in constant time, whether $a_i$ is contained in the interval. This procedure returns us the interval containing $a_i$, and thus, the heap (and bucket) containing $x_i$. $◀$

We prove that the data structure supports all three heap operations within the specified time bounds while maintaining Invariant 1.

To push $x_i$ onto $H$, we set $a_i=t$ and increment $t$. We then add a new Fibonacci heap $F$ to $B[0]$ with $I_F=[a_i,a_i+1)$. Whilst a bucket $B[j]$ contains three Fibonacci heaps, we select its oldest two Fibonacci heaps $F_1,F_2$. We Meld $F_1$ and $F_2$ into a new Fibonacci heap $F^{\prime }$ in worst-case constant time, and we move $F^{\prime }$ to $B[j+1]$. We define the corresponding interval $I_{F^{\prime }}$ as the union of the consecutive intervals $I_{F_1}$ and $I_{F_2}$. Since Property (a) held for both $F_1$ and $F_2$, it now holds for $F^{\prime }$. Moreover, $|I_{F^{\prime }}|=2^{j+1}$ and so Property (b) is maintained. Since, before the update, all intervals collectively partitioned $[0,t)$ and we only added the interval $[t,t+1)$ we maintain Properties (c) and (d). Every Meld operation decreases the number of Fibonacci heaps and every push operation creates only one heap. Hence, each push operation performs amortized $O(1)$ Meld operations.

Finally, we update $M$ and the string $S_M$. After we have merged two heaps in a bucket $B[j]$, only $M[j]$ and $M[j+1]$ change. Moreover, $M[j]$ can only increase in value and $M[j+1]$ can only decrease to at least the original value of $M[j]$. Therefore, all bits $S_M[k]$ for $k\notin \{j,j+1\}$ remain unchanged and we update $S_M$ in amortized constant time. Thus, a push operation takes amortized constant time.

By Lemma 4, we find the Fibonacci heap $F$ and the bucket $B[j]$ that contain $x_i$ in constant time. We perform $F$.DecreaseKey$(x_i,y)$ in amortized constant time. We update $M[j]$ and identify the index $k$ of the leftmost $1$-bit in $S_M$ after index $j$ in constant time using bitstring operations [4]. Note that $S_M[j]=1$ if and only if $M[j]\le M[k]$.

If $S_M[j]=1$, then we recursively find the next for which $S_M[j^{\prime }]=1$ using the same bitstring operation. If , then we set $S_M[j^{\prime }]=0$ and we recurse. If $M[j]\ge M[j^{\prime }]$ then for all with $S_M[j^{\prime \prime }]=1$, $M[j]\ge M[j^{\prime \prime }]$ and our update terminates. The recursive call takes amortized constant time since it can only decrease the number of $1$-bits in $S_M$.

We obtain the index $j$ of the leftmost $1$-bit of $S_M$ in constant time using bitstring operations. Per definition, the minimum key of $H$ is in $B[j]$. We perform the Peak operation on both heaps in $B[j]$. For the heap $F$ containing the minimum key, we do $F$.Pop() in $O(1+\log 2^j)=O(j)$ time to return the element $x_i\in H$ with the minimum key. Finally, we update $M[j]$ and $S_M$. We update $M[j]$ in constant time and iterate from $j$ to $1$. For each iteration $\mathrm{\ell }$, let $k>\mathrm{\ell }$ be the minimum index where $S_M[k]=1$. We obtain $k$ in constant time using bitstring operations and update $S_M[\mathrm{\ell }]$ by comparing $M[\mathrm{\ell }]$ to $M[k]$. Thus, this update takes $O(j)$ time. By Invariant 1, $\log (b_i-a_i)\in O(j)$ and thus the $H$.Pop() takes $O(1+\log (b_i-a_i))$ amortized time. $◀$

We fix the input $(G=(V,E),s,w)$ and execute Dijkstra’s algorithm, which defines a set of $n$ timestamp intervals ${\{[a_i,b_i]\}}_{i\in [n]}$. Each interval $[a_i,b_i]$ has a minimum size of $1$ and corresponds to a unique vertex $x_i\in V\setminus \{s\}$. Dijkstra’s algorithm operates in $O(m+{\sum }_{x_i\in V\setminus \{s\}}(1+\log (b_i-a_i)))$ time. Since any algorithm must spend $\mathrm{\Omega }(n+m)$ time to read the input, it remains to show that $\sum _{x_i\in V\setminus \{s\}}(1+\log (b_i-a_i))\in \mathrm{\Omega }(n+\log \mathrm{\ell }(G,s))$.

Consider the initial execution of Dijkstra’s algorithm on $(G,s,w)$. For each vertex $x_i\in V\setminus \{s\}$, there is a unique edge $(u,x_i)$ that, upon inspection, pushes the element $x_i$ onto the heap $H$. The set of these edges forms a spanning tree $T$ rooted at $s$.

Denote by $\text{rank}(r_i)$ the rank of $r_i$ in the ordered sequence $L$. We construct a new integer edge weighting $w^{\prime }$ such that running Dijkstra’s algorithm on $(G,s,w^{\prime })$ outputs $L$. We set $w^{\prime }(e)=\mathrm{\infty }$ for all edges $e\in E\setminus T$. We then traverse $T$ in a breath-first manner. For each edge $(x_j,x_i)\in T$, we observe that in our original run of Dijkstra’s algorithm, the algorithm popped the vertex $x_j$ before it pushed the vertex $x_i$ onto the heap. It follows that for the intervals $\{[a_j,b_j],[a_i,b_i]\}$, the value $b_j\le a_i$. Since $r_j\in [a_j,b_j]$, $r_i\in [a_i,b_i]$, and $r_j\ne r_i$ we may conclude that $\text{rank}(r_i)>(r_j)$. We assign to each edge $(x_j,x_i)\in T$ the positive edge weight $w^{\prime }((x_j,x_i))=\text{rank}(r_i)-\text{rank}(r_j)$. It follows that the distance in $(G,E,w^{\prime })$ from $s$ to any vertex $x_i$ is equal to $\text{rank}(r_i)$ and so Dijkstra’s algorithm on $(G,s,w^{\prime })$ outputs $L$. $◀$

What remains is to show that the number of ways to select distinct $r_i\in [a_i,b_i]$, correlates with the size of the timestamp intervals. This result was first demonstrated by Cardinal, Fiorini, Joret, Jungers, and Munro [1, the first 2 paragraphs of page 8 of the ArXiV version]. It was later paraphrased in Lemma 4.3 in [5].

To illustrate the simplicity of this lemma, we quote the proof in [5]: For each $i$ between $1$ and $n$ inclusive, choose a real number $r_i$ uniformly at random from the real interval $[0,n]$, independently for each $i$. With probability $1$, the $r_i$ are distinct. Let $L$ be the permutation of $[n]$ obtained by sorting $[n]$ by $r_i$. Each possible permutation is equally likely. If each $r_i\in [a_i,b_i]$ then $L$ is in $Z$. The probability of this happening is ${\prod }_{i=1}^k(b_i-a_i)/n$. It follows that $|Z|\ge n!\cdot {\prod }_{i=1}^n(b_i-a_i)/n$. Taking logarithms gives $\log |Z|\ge {\sum }_{i=1}^n\log (b_i-a_i)+\log n!-n\log n$. By Stirling’s approximation of the factorial, $\log n!\ge n\log n-n\log e$. The lemma follows. $◀$

It follows that we can recreate the main theorem from [6]:

The running time of Dijkstra’s algorithm with the input $(G,s,w)$ is $O(m)$ plus the time needed for push and pop operations. With a timestamp-optimal heap, by Corollary 6, the algorithm thus takes $O(m+\sum _{x_i\in V\setminus \{s\}}(1+\log (b_i-a_i)))$ total time. By Lemma 8, the total running time is then $O(m+n+\log |Z|)$, where $|Z|$ denotes the number of distinct linear orders created by choosing distinct real values $r_i\in [a_i,b_i]$. By Lemma 7: $|Z|\le \mathrm{\ell }(G,s)$, and so Dijkstra’s algorithm with any timestamp-optimal heap runs in $O(m+n+\log \mathrm{\ell }(G,s))$ time. Conversely, any algorithm that solves SSSP needs $\mathrm{\Omega }(m+n)$ time to read the input, and $\mathrm{\Omega }(\log \mathrm{\ell }(G,s))$ is an information-theoretical universal lower bound. $◀$