A scaling algorithm solves a problem by initially considering only the highest-order 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, ν) ˆˆ E {w (u, ν)}. 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 = Œˆlg (W + 1)Œ‰ be the number of bits in the binary representation of W, and for i = 1, 2, . . . ,k, let w_i (u, ν) = ŒŠw(u, ν)/2^k-iŒ‹. That is, w_i (u, ν) is the "scaled-down" version of w (u, ν) given by the i most significant bits of w (u, ν). (Thus, w_k(u, ν) = w(u, ν) for all (u, ν) ˆˆ E.) For example, if k = 5 and w(u, ν) = 25, which has the binary representation Œ©11001Œª, then w₃(u, ν) = Œ©110Œª = 6. As another example with k = 5, if w(u, ν) = Œ©00100Œª = 4, then w₃(u, ν) = Œ©001Œª = 1. Let us define Î´_i (u, ν) as the shortest-path weight from vertex u to vertex ν using weight function w_i. Thus, Î´_k (u, ν) = Î´(u, ν) for all u, ν ˆˆ V. For a given source vertex s, the scaling algorithm first computes the shortest-path weights Î´₁ (s, ν) for all ν ˆˆ V, then computes Î´₂ (s, ν) for all ν ˆˆ V, and so on, until it computes Î´_k (s, ν) for all ν ˆˆ V. We assume throughout that |E| ‰¤ |V| ˆ’ 1, and we shall see that computing δ_i from δ_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, we have Î´(s, ν) ‰¤ |E|. Show that we can compute Î´(s, ν) for all ν ˆˆ V in O(E) time.

b. Show that we can compute Î´₁(s, ν) for all ν ˆˆ V in O(E) time.

Let us now focus on computing Î´_i from δ_i-1.

c. Prove that for i = 2, 3, . . . ,k, we have either w_i (u, ν) = 2w_i-1 (u, ν) or w_i (u, ν) = 2w_i-1(u, ν) + 1. Then, prove that

for all ν ˆˆ V.

d. Define for i = 2, 3, . . . ,k and all (u, ν) ˆˆ E,

Prove that for i = 2, 3, . . . ,k and all u, ν ˆˆ V, the "re-weighted" value wÌ‚_i (u, ν) of edge (u, ν) is a nonnegative integer.

e. Now, define δ̂_i (s, ν) as the shortest-path weight from s to ν using the weight function wÌ‚_i. Prove that for i = 2, 3, . . . ,k and all ν ˆˆ V,

f. Show how to compute δ_i (s, ν) from δ_i-1 (s, ν) for all ν ˆˆ V in O(E) time, and conclude that we can compute δ (s, ν) for all ν ˆˆ V in O(E lg W) time.

Transcribed Image Text:

28;–1 (s, v) < 8;(s, v) < 28;–1(s, v) +|V|– 1 Ф: (и, v) — w:(и, v) + 28,-1 (s, и) — 28,—1 (s, v) .