# 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.** 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:

- If all edge weights are multiplied by a factor of $c$, then all shortest-path weights are multiplied by $c$.
- 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:

- Compute the weights $\hat w_i(u, v)$ in $O(E)$ time, as shown in part (d).
- 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.
- 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:

- Compute $\delta_1(s, v)$ for all $v \in V$. As shown in part (b), this takes $O(E)$ time.
- 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)$.