24-4 Gabow's scaling algorithm for single-source shortest paths

A scaling algorithm solves a problem by initially considering only the highestorder bit of each relevant input value (such as an edge weight). It then refines the initial solution by looking at the two highest-order bits. It progressively looks at more and more high-order bits, refining the solution each time, until it has examined all bits and computed the correct solution.

In this problem, we examine an algorithm for computing the shortest paths from a single source by scaling edge weights. We are given a directed graph $G = (V, E)$ with nonnegative integer edge weights $w$. Let $W = \max_{(u, v) \in E} \{w(u, v)\}$. Our goal is to develop an algorithm that runs in $O(E\lg W)$ time. We assume that all vertices are reachable from the source.

The algorithm uncovers the bits in the binary representation of the edge weights one at a time, from the most significant bit to the least significant bit. Specifically, let $k = \lceil \lg(W + 1) \rceil$ be the number of bits in the binary representation of $W$, and for $i = 1, 2, \ldots, k$, let $w_i(u, v) = \lfloor w(u, v) / 2^{k - i} \rfloor$. That is, $w_i(u, v)$ is the "scaled-down" version of $w(u, v)$ given by the $i$ most significant bits of $w(u, v)$. (Thus, $w_k(u, v) = w(u, v)$ for all $(u, v) \in E$.) For example, if $k = 5$ and $w(u, v) = 25$, which has the binary representation $\langle 11001 \rangle$, then $w_3(u, v) = \langle 110 \rangle = 6$. As another example with $k = 5$, if $w(u, v) = \langle 00100 \rangle = 4$, then $w_3(u, v) = \langle 001 \rangle = 1$. Let us define $\delta_i(u, v)$ as the shortest-path weight from vertex $u$ to vertex $v$ using weight function $w_i$. Thus, $\delta_k(u, v) = \delta(u, v)$ for all $u, v \in V$. For a given source vertex $s$, the scaling algorithm first computes the shortest-path weights $\delta_1(s, v)$ for all $v \in V$, then computes $\delta_2(s, v)$ for all $v \in V$, and so on, until it computes $\delta_k(s, v)$ for all $v \in V$. We assume throughout that $|E| \ge |V| - 1$, and we shall see that computing $\delta_i$ from $\delta_{i - 1}$ takes $O(E)$ time, so that the entire algorithm takes $O(kE) = O(E\lg W)$ time.

a. Suppose that for all vertices $v \in V$, we have $\delta(s, v) \le |E|$. Show that we can compute $\delta(s, v)$ for all $v \in V$ in $O(E)$ time.

b. Show that we can compute $\delta_1(s, v)$ for all $v \in V$ in $O(E)$ time.

Let us now focus on computing $\delta_i$ from $\delta_{i - 1}$.

c. Prove that for $i = 2, 3, \ldots, k$, we have either $w_i(u, v) = 2w_{i - 1}(u, v)$ or $w_i(u, v) = 2w_{i - 1}(u, v) + 1$. Then, prove that

$$2\delta_{i - 1}(s, v) \le \delta_i(s, v) \le 2\delta_{i - 1}(s, v) + |V| - 1$$

for all $v \in V$.

d. Define for $i = 2, 3, \ldots, k$ and all $(u, v) \in E$,

$$\hat w_i = w_i(u, v) + 2\delta_{i - 1}(s, u) - 2\delta_{i - 1}(s, v).$$

Prove that for $i = 2, 3, \ldots, k$ and all $u, v \in V$, the "reweighted" value $\hat w_i(u, v)$ of edge $(u, v)$ is a nonnegative integer.

e. Now, define $\hat\delta_i(s, v)$ as the shortest-path weight from $s$ to $v$ using the weight function $\hat w_i$. Prove that for $i = 2, 3, \ldots, k$ and all $v \in V$,

$$\delta_i(s, v) = \hat\delta_i(s, v) + 2\delta_{i - 1}(s, v)$$

and that $\hat\delta_i(s, v) \le |E|$.

f. Show how to compute $\delta_i(s, v)$ from $\delta_{i - 1}(s, v)$ for all $v \in V$ in $O(E)$ time, and conclude that we can compute $\delta(s, v)$ for all $v \in V$ in $O(E\lg W)$ time.

a. Since all weights are nonnegative, use Dijkstra's algorithm. Implement the priority queue as an array $Q[0..|E| + 1]$, where $Q[i]$ is a list of vertices $v$ for which $v.d = i$. Initialize $v.d$ for $v \ne s$ to $|E| + 1$ instead of to $\infty$, so that all vertices have a place in $Q$. (Any initial $v.d > \delta(s, v)$ works in the algorithm, since $v.d$ decreases until it reaches $\delta(s, v)$.)

The $|V|$ $\text{EXTRACT-MIN}$s can be done in $O(E)$ total time, and decreasing a $d$ value during relaxation can be done in $O(1)$ time, for a total running time of $O(E)$.

  • When $v.d$ decreases, just add $v$ to the front of the list in $Q[v.d]$.
  • $\text{EXTRACT-MIN}$ removes the head of the list in the first nonempty slot of $Q$. To do $\text{EXTRACT-MIN}$ without scanning all of $Q$, keep track of the smallest $i$ for which $Q[i]$ is not empty. The key point is that when $v.d$ decreases due to relaxation of edge $(u, v)$, $v.d$ remains $u.d$, so it never moves to an earlier slot of $Q$ than the one that had $u$, the previous minimum. Thus $\text{EXTRACT-MIN}$ can always scan upward in the array, taking a total of $O(E)$ time for all $\text{EXTRACT-MIN}$s.

b. For all $(u, v) \in E$, we have $w_1(u, v) \in \{0, 1\}$, so $\delta_1(s, v) \le |V| - 1 \le |E|$. Use part (a) to get the $O(E)$ time bound.

c. To show that $w_i(u, v) = 2w_{i - 1}(u, v)$ or $w_i(u, v) = 2w_{i - 1}(u, v) + 1$, observe that the $i$ bits of $w_i(u, v)$ consist of the $i - 1$ bits of $w_{i - 1}(u, v)$ followed by one more bit. If that low-order bit is $0$, then $w_i(u, v) = 2w_{i - 1}(u, v)$; if it is $1$, then $w_i(u, v) = 2w_{i - 1}(u, v) + 1$.

Notice the following two properties of shortest paths:

  1. If all edge weights are multiplied by a factor of $c$, then all shortest-path weights are multiplied by $c$.
  2. If all edge weights are increased by at most $c$, then all shortest-path weights are increased by at most $c(|V| - 1)$, since all shortest paths have at most $|V| - 1$ edges.

The lowest possible value for $w_i(u, v)$ is $2w_{i - 1}(u, v)$, so by the first observation, the lowest possible value for $\delta_i(s, v)$ is $2\delta_{i - 1}(s, v)$.

The highest possible value for $w_i(u, v)$ is $2w_{i - 1}(u, v) + 1$. Therefore, using the two observations together, the highest possible value for $\delta_i(s, v)$ is $2\delta_{i - 1}(s, v) + |V| - 1$

d. We have

$$ \begin{aligned} \hat w_i(u, v) & = w_i(u, v) + 2\delta_{i - 1}(s, u) - 2\delta_{i - 1}(s, v) \\ & \ge 2w_{i - 1}(u, v) + 2\delta_{i - 1}(s, u) - 2\delta_{i - 1}(s, v) \\ & \ge 0. \end{aligned} $$

The second line follows from part (c), and the third line follows from Lemma 24.10: $\delta_{i - 1}(s, v) \le \delta_{i - 1}(s, u) + w_{i - 1}(u, v)$.

e. Observe that if we compute $\hat w_i(p)$ for any path $p:u \leadsto v$, the terms $\delta_{i - 1}(s, t)$ cancel for every intermediate vertex $t$ on the path. Thus,

$$\hat w_i(p) = w_i(p) + 2\delta_{i - 1}(s, u) - 2\delta_{i - 1}(s, v).$$

(This relationship will be shown in detail in equation ($\text{25.10}$) within the proof of Lemma 25.1.) The $\delta_{i - 1}$ terms depend only on $u$, $v$, and $s$, but not on the path $p$; therefore the same paths will be of minimum $w_i$ weight and of minimum $\hat w_i$ weight between $u$ and $v$. Letting $u = s$, we get

$$ \begin{aligned} \hat\delta_i(s, v) & = \delta_i(s, v) + 2\delta_{i - 1}(s, s) - 2\delta_{i - 1}(s, v) \\ & = \delta_i(s, v) - 2\delta_{i - 1}(s, v). \end{aligned} $$

Rewriting this result as $\delta_i(s, v) = \hat\delta_i(s, v) + 2\delta_{i - 1}(s, v)$ and combining it with $\delta_i(s, v) \le 2\delta_{i - 1}(s, v) + |V| - 1$ (from part (c)) gives us $\hat\delta_i(s, v) \le |V| - 1 \le |E|$.

f. To compute $\delta_i(s, v)$ from $\delta_{i - 1}(s, v)$ for all $v \in V$ in $O(E)$ time:

  1. Compute the weights $\hat w_i(u, v)$ in $O(E)$ time, as shown in part (d).
  2. By part (e), $\hat\delta_i(s, v) \le |E|$, so use part (a) to compute all $\hat\delta_i(s, v)$ in $O(E)$ time.
  3. Compute all $\delta_i(s, v)$ from $\hat\delta_i(s, v)$ and $\delta_{i - 1}(s, v)$ as shown in part (e), in $O(V)$ time.

To compute all $\delta(s, v)$ in $O(E\lg W)$ time:

  1. Compute $\delta_1(s, v)$ for all $v \in V$. As shown in part (b), this takes $O(E)$ time.
  2. For each $i = 2, 3, \ldots, k$, compute all $\delta_i(s, v)$ from $\delta_{i - 1}(s, v)$ in $O(E)$ time as shown above. This procedure computes $\delta(s, v) = \delta_k(u, v)$ in time $O(Ek) = O(E\lg W)$.