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

A

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.scalingIn 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.