A Faster Directed Single-Source Shortest Path Algorithm

Let us begin with Dijkstra’s algorithm, which maintains a “frontier” $S$ of vertices, such that if a vertex is “incomplete” – meaning its current distance label is greater than its true distance – then its shortest path visits some complete vertex in $S$. In other words, the frontier encloses a set of vertices sufficient for finding the shortest paths of all remaining incomplete vertices.

Dijkstra’s algorithm each time extracts from the frontier the vertex with smallest distance label, which is guaranteed to be complete. It then relaxes all out-going edges and adds these neighbors to frontier. This produces an ordering of all vertices by distances, creating an inherent $\mathrm{\Omega }(n\log n)$ sorting barrier.

The breakthrough in [10] overcomes this barrier by introducing a divide-and-conquer procedure with $(\log n)/t$ levels, namely Bounded Multi-Source Shortest Path (BMSSP), which operates on a “frontier” $S$ with respect to a bound $B$. BMSSP aims to settle all vertices in . It recursively invokes subcalls of BMSSP on sets consisting of the smallest $1/2^t$ fraction of vertices extracted from the frontier. A naïve implementation would still spend $\mathrm{\Theta }(t)$ time on each frontier vertex, yielding a total running time of $\mathrm{\Theta }(\log n)$ per vertex.

To solve this problem, [10] reduces the size of frontier $S$ by a factor $1/k$ relative to the target set $\tilde{U}$, by running Bellman-Ford algorithm for $k$ iterations. Any remaining incomplete vertex must lie in the shortest path tree of some $x\in S$ with size at least $k$. Such vertices $x$ are called “pivots”, and their number is bounded by $|\tilde{U}|/k$. However, this approach still poses a bottleneck since Bellman-Ford requires $\mathrm{\Omega }(k)$ time per vertex on average. This cost seems unavoidable, because the algorithm needs to determine, for each vertex $v\in \tilde{U}$, which pivot’s shortest path tree it belongs to.

A key observation is that, such explicit mapping is unnecessary. Our new insight is that we can construct a spanning forest that connects the frontier $S$ via local Dijkstra searches from $S$, and partition it into edge-disjoint subtrees of sizes $\mathrm{\Theta }(k)$. This idea is inspired by [9] that tackles the single-source bottleneck path (SSBP) problem, and reduces the cost of finding pivots from $O(k)$ to $O(\log k)$ per vertex. Then, for each subtree, the algorithm only tracks the vertex with the smallest distance label, referred to as a “pivot”, which serves as a handle for the vertices in its corresponding subtree. Then we are able to maintain $1/k$ of the vertices in $S$ in the partial-sorting data structure, and meanwhile efficiently select a minimum subset of the whole frontier. For other vertices, we only need to check whether they fit the range of the subset without sorting them. Then the time for inserting a vertex in the data structure can be amortized to an edge on the subtree containing it, but that edge is not supposed to be in recursive subcalls. So the overall running time is roughly $O(m\sqrt{\log n})$. However, in this recursive procedure for shortest path, the upper bound $B$ used for each invocation is dynamically generated. If the range by bound $B$ contains too many vertices with respect to $S$, the algorithm can only perform partial execution, and some vertices may be reinserted into $S$ after extraction. This behavior must be handled carefully to achieve the running time mentioned above.

Single-source shortest path has been extensively studied in various special cases. Pettie and Ramachandran [22] proposed an algorithm running in $O(m\alpha (m,n)+\min \{n\log n,n\log \log r\})$ time for undirected graphs, where $\alpha$ is the inverse-Ackermann function and $r$ is the max-min ratio of edge weights. In word-RAM model with bounded integer edge weights, a sequence of works [15, 16, 26, 23, 24, 27, 19] culminated in Thorup’s linear-time algorithm for undirected graphs [25] and $O(m+n\log \log \min \{n,C\})$-time algorithm for directed graphs [28], where $C$ is the maximum edge weight.

If negative edge weights are allowed, the Bellman-Ford algorithm [1] needs $O(mn)$ time. Beyond this, there are nearly linear time algorithms for integer weights (with respect to bit complexity) [5, 2, 4], and strongly subcubic time algorithms for real weights [12, 20, 21].

For any degree bound $3\le \delta \le \frac{m}{n}$, we preprocess $G$ in $O(m)$ time to a graph with $O(m)$ edges, $O(m/\delta )$ vertices, and maximum (in- and out-) degree bounded by $\delta$, while preserving all shortest path lengths. A classical way to achieve this, similar to that in [13], proceeds as follows:

• $\mathrm{■}$

  Substitute each $v$ with a zero-weighted cycle $C_v$ of $\lceil \frac{{\mathrm{\Delta }}_v}{\delta -2}\rceil$ vertices, where ${\mathrm{\Delta }}_v$ denotes the degree of $v$. For each $v$’s neighbor $u$ (either incoming or outgoing), assign one vertex in $C_v$ to represent the edge between them, denoted as $x_{vu}$; make sure each vertex in $C_v$ represents at most $\delta -2$ different $x_{vu}$.

• $\mathrm{■}$

  For every edge $(u,v)\in G$, add a directed edge from vertex $x_{uv}$ to $x_{vu}$ with weight $w_{uv}$.

Note that when $m\ge n\log n$, Dijkstra’s algorithm implemented with Fibonacci heap already reaches the optimal time $O(m+n\log n)=O(m)$, thus it suffices to consider the regime $m\le n\log n$ in our algorithm.

Our algorithm works under the comparison-addition model, in which edge weights can only be compared or added, each taking $O(1)$ time. No other arithmetic or algebraic operations on edge weights are allowed.

We maintain global distance labels $d[v]$ for all vertices $v\in V$. Initially $d[s]=0$ and $d[v]=\mathrm{\infty }$ for all $v\ne s$. All updates to $d[v]$ are through relaxation: $d[v]\leftarrow \min \{d[v],d[u]+w_{uv}\}$ of some edge $(u,v)\in E$. A relaxation is valid, if $d[v]$ was updated, namely $d[u]+w_{uv}\le d[v]$. In our algorithm, we also introduce an upper bound $B$ and require to prevent immature modification. Hence, $d[v]$ is non-increasing and always corresponds to the length of some path from $s$ to $v$. Let $\mathrm{𝚍𝚒𝚜}(v)$ denote the length of the true shortest path from source $s$ to $v$, then $d[v]\ge \mathrm{𝚍𝚒𝚜}(v)$ always holds.

Similar to previous works [6, 10], for clarity in presenting the algorithm, we define a tie-breaking rule for comparing distance labels in order to:

1. 1.

   Keep the structure of the shortest path tree throughout the algorithm;

2. 2.

   Establish a relative ordering among the vertices with identical $d[]$.

In principle, we treat a path of length $l$ that traverses $q$ edges, represented by the vertices $v_0=s,v_1,\mathrm{\dots },v_q$, as a tuple $⟨l,q,v_q,v_{q-1},\mathrm{\dots },v_0⟩$, where vertices are listed in reverse order, and sort them based on the lexicographical order. However, it turned out that the first 4 items of the above tuple are sufficient for tie-breaking: path length ($\mathrm{𝚕𝚎𝚗𝚐𝚝𝚑}$), number of edges ($\mathrm{𝚗𝙴𝚍𝚐𝚎𝚜}$), $v$ itself ($\mathrm{𝚌𝚞𝚛𝚛}$), and $v$’s predecessor ($\mathrm{𝚙𝚛𝚎𝚍}$). This is because our algorithm performs such comparisons in the following scenarios:

Relaxing an edge $(u,v)$:

If $u\ne d[v].\mathrm{𝚙𝚛𝚎𝚍}$, even if $\mathrm{𝚕𝚎𝚗𝚐𝚝𝚑}$ and $\mathrm{𝚗𝙴𝚍𝚐𝚎𝚜}$ are tied, it suffices to compare $u$ and $d[v].\mathrm{𝚙𝚛𝚎𝚍}$; if $u=d[v].\mathrm{𝚙𝚛𝚎𝚍}$, then $d[u]$ has been updated to currently “shortest” and $d[v]$ must get updated accordingly;

Comparing two different $d[u]$ and $d[v]$ for $u\ne v$:

In this case $\mathrm{𝚌𝚞𝚛𝚛}$ acts as a tie-breaker.

Upper bound $B$:

In the algorithm the upper bound $B$ is also represented by such a 4-tuple.

Algorithm 1 illustrates how an edge $(u,v)$ is relaxed. Note that an upper bound $B$ is introduced to prevent premature update of vertices whose tentative distances exceed the current bound in the main algorithm.

For a vertex $v$, if $d[v]=\mathrm{𝚍𝚒𝚜}(v)$, we say $v$ is complete. If all vertices in a set are complete, we say that set is complete. We need to specify the time step when referring to $d[v]$ and completeness because they are sensitive to the algorithm progress.

Let $S\subseteq V$ be a set of vertices and $B$ be a bound. We define $\tilde{U}=\tilde{U}(B,S)$ the set of every vertex $v$ such that and the shortest path of $v$ visits some vertex in $S$. The goal is to make $\tilde{U}$ complete.

Additionally, for a vertex set $U\subseteq V$ and any bound $B$, define $d_B[U]=\min (\{B\}\cup \{d[x]:x\in U\})$ and ${\mathrm{𝚍𝚒𝚜}}_B(U)=\min (\{B\}\cup \{\mathrm{𝚍𝚒𝚜}(x):x\in U\})$. ($B$ is introduced here in case $U$ is an empty set.)

We introduce frontier, which is crucial for understanding our algorithm. This concept also appeared in [10]: at any moment and, for two sets $X,Y\subseteq \tilde{U}$, we say is a frontier for $\tilde{U}$, if any $v\in \tilde{U}$ satisfies at least one of the following:

1. 1.

   $v\in X$ and $v$ is complete;

2. 2.

   the shortest path of $v$ visits some complete vertex (possibly itself) in $Y$.

Note $X$ is not necessarily complete; but any incomplete vertex of $X$ must satisfy the second condition. Based on the definition, we can make the following observations:

Proof sketch: the first observation lies from the fact that when a vertex becomes complete, it continues to be complete ever since. The second observation is because the vertex with minimum distance label $d[]$ in $Y$ must be complete. The third observation is because: for any vertex in $\tilde{U}(B,Y)$, its shortest path visits some vertex $y$ in $Y$; and the shortest path of $y$, as a prefix of the shortest path of $v$, owing to $Y\subseteq \tilde{U}=\tilde{U}(B,S)$, visits some vertex in $S$, so the shortest path of $v$ visits $S$; The fourth observation is because: for any incomplete vertex in $\tilde{U}(B,Y)$, it is also in $\tilde{U}(B,S)$, then its shortest path visits some complete vertex in $Y$; for any complete vertex $v$ in $\tilde{U}(B,Y)$, by definition its shortest path visits some vertex $y\in Y$, and $y$ must be complete as $v$ is complete. The fifth is because if the distance of a vertex is less than $d_B[Y]$, then it cannot visit any complete vertex in $Y$.

We found that Dijkstra’s algorithm, [10] and our algorithm can be restated under a unified framework:

1. (1)

   Given a frontier for $\tilde{U}=\tilde{U}(B,S)$. Our goal is to make $\tilde{U}$ complete;

2. (2)

   Identify a complete set $Z\subseteq \tilde{U}$; or make $Z$ complete, possibly after performing some relaxations;

3. (3)

   Relax the outgoing edges from $Z$ and denote $R$ as the set of out-going neighbors of $Z$ but not in $Z$ with distances less than $B$, and relaxations from $Z$ to them are valid. Clearly $R\subseteq \tilde{U}$;

4. (4)

   Update to a new frontier for $\tilde{U}$ as ;

5. (5)

   Return to the first step and repeat the process until $Y=\mathrm{\varnothing }$, then $\tilde{U}=X$ is complete.

We show that for $Z$ given by (2), after operations in (3), is indeed a frontier for $\tilde{U}$. Since adding vertices never violates frontier conditions, it suffices to verify for $v\in \tilde{U}$ whose shortest path visits some complete $u\in Z$ such that $u$ is in $Y$ but removed from $Y^{\prime }$, $v$ still satisfy one of the two frontier conditions.

• $\mathrm{■}$

  If $v\in Z$, we are already done;

• $\mathrm{■}$

  If $v\notin Z$, since $u\in Z$, along the shortest path from $u$ to $v$, there must exist two adjacent vertices $x$ and $y$ such that $x\in Z$ and $y\notin Z$; then $y$ is in $R$ and added to $Y^{\prime }$, ensuring that the shortest path of $v$ still visits a complete vertex $y\in Y^{\prime }$.

The efficiency of the algorithm depends critically on how we can efficiently identify $Z$ or make $Z$ complete. In Dijkstra’s algorithm, the smallest vertex $\arg {\min }_{x\in Y}d[x]$ is guaranteed to be complete. Therefore, the algorithm organizes $Y$ using a priority queue and simply selects such $x$ to form $Z$. In [10] and our approach, the algorithm repeatedly selects a subset of smallest vertices $S_i$ from the frontier, and recursively invoke a lower-level algorithm on $S_i$ to obtain a complete set $U_i$, which is then used to update the frontier.

Recall that we hope to manage the frontier more efficiently. As mentioned in Section 1.1, Algorithm 2 tries to connect $S$ with edge-disjoint $\mathrm{\Theta }(k)$ sized sub-trees. We perform a local Dijkstra search from every vertex $x\in S$, only adding edges with valid relaxation into the sub-tree. There are three possible cases:

• $\mathrm{■}$

  If at least $k$ vertices are found, we stop and record the result as a directed tree ${\overline{F}}_j$;

• $\mathrm{■}$

  If the search encounters a vertex that already belongs to an existing ${\overline{F}}_j$ (i.e., it overlaps with an existing sub-tree), we stop and merge the current explored sub-tree with that ${\overline{F}}_j$;

• $\mathrm{■}$

  Otherwise the search fails to reach $k$ vertices from $x$, we record it as an arborescence $W_j$.

Finally we partition each ${\overline{F}}_j$ into $\mathrm{\Theta }(k)$ sized edge-disjoint sub-trees in linear time as described in Section 4.1.

An important observation is that, under a full execution, if the search fails to reach $k$ vertices from $x$, we no longer need to initiate any further search from $x$ at current value $d[x]$ with bound $B$.

• $\mathrm{■}$

  If $x$ is currently complete, every vertex $v$ with whose shortest path visits $x$ is already reached and updated;

• $\mathrm{■}$

  Otherwise, the shortest path of $x$ passes through some other complete vertex in $S$. We can rely on that vertex instead of $x$ for subsequent shortest path relaxations.

Therefore, $x$ is no longer useful for relaxation; unless $d[x]$ is updated by another relaxation and then $x$ reappears in $S$ in a subsequent call. Intuitively, each search from $x$ failing to reach $k$ vertices is attributed to one of $x$’s incoming edges, so it occurs at most $\delta$ times. This statement is formally proved in Lemma 11.

[10] designed a data structure to support the operations required for partially sorting the “frontiers”. In this section we present a simpler data structure with a slight improvement. We implement by a self-balanced binary search tree (BST) of $M$-sized blocks: blocks sorted by the BST, but items inside a block unsorted. Requiring $\log (N/M)\le M$, an $O(\log (N/M))$ time BST operation is amortized to $O(1)$ per item in blocks, which enables us to perform operations except insertions in amortized linear time.

The proof of Lemma 6 is given in Section 4.2.

In this section we are ready to present our main BMSSP algorithm, see Algorithm 3.

The base case ($l=0$) can be solved using Dijkstra’s algorithm as in Section 3.7. Now we assume $l>0$.

We first initialize data structure $𝒟$ with parameter $M=t{2}^{(l-1)t}$ to hold the vertices we will scan.

Then we run FindPivots of Lemma 4 to reorganize $S$ into disjoint subsets ${\{P_j\}}_{j=1}^p$ and $Q$ of $S$, with a set $W$. For each $P_j$ we find $p_j=\arg {\min }_{x\in P_j}d[x]$ the minimum vertex in it. We will update $p_j$ accordingly such that $p_j$ always lower bounds necessary ²²2By “necessary” we mean a vertex in $P_j$ whose shortest path does not visit any complete vertex in $𝒟$; because if it does visit, such a vertex need not to be tracked. For better readability, we recommend that readers first form a high-level picture of the algorithm and then return to this definition. A formal proof that the algorithm preserves this property appears in Lemma 9. vertices in $P_j$.

Set $B^{\prime }\leftarrow B_0^{\prime }\stackrel{\mathrm{def}}{=}\min \{B,\{d[p_j]:1\le j\le p\}\}$; $U\leftarrow \mathrm{\varnothing }$. $B^{\prime }$ actually marks the progress of our algorithm. $U$ will accumulate batches of complete vertices. Set $J\leftarrow \mathrm{\varnothing }$; $J$ holds the set of $j$ such that $p_j$ needs to be re-selected. The rest of algorithm repeats the following steps for multiple rounds until $𝒟$ becomes empty or $\left|U\right|>t^3{2}^{lt}$, where during the $i-$th iteration ($i\ge 1$), we:

• $\mathrm{■}$

  Pull from $𝒟$ a subset $S_i$ of keys with smallest values in $𝒟$ upper bounded by $B_i$ (also a lower bound for remaining vertices in $𝒟$). Scan $x\in S_i$; if $x=p_j$ for some $j$, add into $S_i$ (by brute-force search);

• $\mathrm{■}$

  Recursively call BMSSP($B_i,S_i,l-1$) and collect its output $B_i^{\prime },U_i,{𝒟}_i$;

• $\mathrm{■}$

  Merge vertices of ${𝒟}_i$ into $𝒟$;

• $\mathrm{■}$

  For each $u\in U_i$, if $u\in P_j$ for some $j$, remove $u$ from $P_j$; and if $u=p_j$, also add $j$ into $J$.

• $\mathrm{■}$

  For each $u\in U_i$, relax every edge $(u,v)$ such that $d[u]+w_{uv}\in [B_i,B)$; if the relaxation is valid, insert into $𝒟$; if $v\in P_j$ for some $j\notin J$, also update $p_j$ to the smaller one between $v$ and $p_j$;

• $\mathrm{■}$

  For each non-empty $P_j$ from $j\in J$, re-select $p_j$ to the minimum vertex in $P_j$ by brute-force search and insert it into $𝒟$;

• $\mathrm{■}$

  Update $U$ to include $U_i$ and $B^{\prime }\leftarrow B_i^{\prime }$; Reset $J\leftarrow \mathrm{\varnothing }$;

• $\mathrm{■}$

  If $𝒟$ becomes empty, then this is a full execution and we quit the loop;

• $\mathrm{■}$

  If $\left|U\right|>t^3{2}^{lt}$, this is a partial execution where we encountered a large workload. Also quit the loop.

After quitting the loop, we operate the following finalizing operations:

• $\mathrm{■}$

  For every $x\in S$ such that $d[x]\in [B^{\prime },B)$, insert into $𝒟$.

• $\mathrm{■}$

  For every edge $(u,v)$ from every such that $d[u]+w_{uv}\in [B^{\prime },B)$, relax it; if the relaxation is valid, insert into $𝒟$.

• $\mathrm{■}$

  $U\leftarrow U\cup W^{\prime }$, i.e., add every vertex $u\in W^{\prime }$ into $U$.

We first present some informal explanations to give reader an intuitive overview on the algorithm, and in subsequent subsections we will provide more formal proofs on correctness and running time.

In this section we verify Algorithm 3 fits the Dijkstra-like algorithm framework proposed in Section 2.5.

Lemma 8 explains why we can invoke a recursive call on a smallest set extracted from the frontier.