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. We can do this in $O(E)$ by the algorithm described in exercise 24.3-8 since our "priority queue" takes on only integer values and is bounded in size by $E$.

b. We can do this in $O(E)$ by the algorithm described in exercise 24.3-8 since $w$ takes values in $\{0, 1\}$ and $V = O(E)$.

c. If the $i$th digit, read from left to right, of $w(u, v)$ is $0$, then $w_i(u, v) = 2w_{i − 1}(u, v)$. If it is a $1$, then $w_i(u, v) = 2w_{i − 1}(u, v) + 1$. Now let $s = v_0, v_1, \dots, v_n = v$ be a shortest path from $s$ to $v$ under $w_i$. Note that any shortest path under $w_i$ is necessarily also a shortest path under $w_{i − 1}$. Then we have

$$\begin{aligned} \delta_i(s, v) & = \sum_{m = 1}^n w_i(v_{m − 1}, v_m) \\ & \le \sum_{m = 1}^n [2w_{i − 1}(u, v) + 1] \\ & \le \sum_{m = 1}^n w_{i − 1}(u, v) + n \\ & \le 2\delta_{i − 1}(s, v) + |V| − 1. \end{aligned}$$

On the other hand, we also have

$$\begin{aligned} \delta_i(s, v) & = \sum_{m = 1}^n w_i(v_{m - 1}, v_m) \\ & \ge \sum_{m = 1}^n 2w_{i - 1}(v_{m - 1}, v_m) \\ & \ge 2\delta_{i - 1}(s, v). \end{aligned}$$

d. Note that every quantity in the definition of $\hat w_i$ is an integer, so $\hat w_i$ is clearly an integer. Since $w_i(u, v) \ge 2w_{i - 1}(u, v)$, it will suffice to show that $w_{i - 1}(u, v) + \delta_{i - 1}(s, u) \ge \delta_{i - 1}(s, v)$ to prove nonnegativity. This follows immediately from the triangle inequality.

e. First note that $s = v_0, v_1, \dots, v_n = v$ is a shortest path from $s$ to $v$ with respect to $\hatw$ if and only if it is a shortest path with respect to $w$. Then we have

$$\begin{aligned} \hat\delta_i(s, v) & = \sum_{m = 1}^n w_i(v_{m - 1}, v_m) + 2\delta_{i - 1}(s, v_{m - 1}) − 2\delta_{i - 1}(s, v_m) \\ & = \sum_{m = 1}^n w_i(v_{m - 1}, v_m) − 2\delta_{i - 1}(s, v_n) \\ & = \delta_i(s, v) − 2\delta_{i - 1}(s, v). \end{aligned}$$

f. By part (a) we can compute $\hat\delta_i(s, v)$ for all $v \in V$ in $O(E)$ time. If we have already computed $\delta_i - 1$ then we can compute $\delta_i$ in $O(E)$ time. Since we can compute $\delta_1$ in $O(E)$ by part b, we can compute $\delta_i$ from scratch in $O(iE)$ time. Thus, we can compute $\delta = \delta_k$ in $O(Ek) = O(E\lg W)$ time.