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)Ew(u,v). Our goal is to develop an algorithm that runs in O(ElgW) 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 wi(u,v)=w(u,v)/2ki. That is, wi(u,v) is the "scaled-down" version of w(u,v) given by the i most significant bits of w(u,v). (Thus, wk(u,v)=w(u,v) for all (u,v)E.) For example, if k=5 and w(u,v)=25, which has the binary representation 11001, then w3(u,v)=110=6. As another example with k=5, if w(u,v)=00100=4, then w3(u,v)=001=1. Let us define δi(u,v) as the shortest-path weight from vertex u to vertex v using weight function wi. Thus, δk(u,v)=δ(u,v) for all u,vV. For a given source vertex s, the scaling algorithm first computes the shortest-path weights δ1(s,v) for all vV, then computes δ2(s,v) for all vV, and so on, until it computes δk(s,v) for all vV. We assume throughout that |E||V|1, and we shall see that computing δi from δi1 takes O(E) time, so that the entire algorithm takes O(kE)=O(ElgW) time.

a. Suppose that for all vertices vV, we have δ(s,v)|E|. Show that we can compute δ(s,v) for all vV in O(E) time.

b. Show that we can compute δ1(s,v) for all vV in O(E) time.

Let us now focus on computing δi from δi1.

c. Prove that for i=2,3,,k, we have either wi(u,v)=2wi1(u,v) or wi(u,v)=2wi1(u,v)+1. Then, prove that

2δi1(s,v)δi(s,v)2δi1(s,v)+|V|1

for all vV.

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

w^i=wi(u,v)+2δi1(s,u)2δi1(s,v).

Prove that for i=2,3,,k and all u,vV, the "reweighted" value w^i(u,v) of edge (u,v) is a nonnegative integer.

e. Now, define δ^i(s,v) as the shortest-path weight from s to v using the weight function w^i. Prove that for i=2,3,,k and all vV,

δi(s,v)=δ^i(s,v)+2δi1(s,v)

and that δ^i(s,v)|E|.

f. Show how to compute δi(s,v) from δi1(s,v) for all vV in O(E) time, and conclude that we can compute δ(s,v) for all vV in O(ElgW) 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 ith digit, read from left to right, of w(u,v) is 0, then wi(u,v)=2wi1(u,v). If it is a 1, then wi(u,v)=2wi1(u,v)+1. Now let s=v0,v1,,vn=v be a shortest path from s to v under wi. Note that any shortest path under wi is necessarily also a shortest path under wi1. Then we have

δi(s,v)=m=1nwi(vm1,vm)m=1n[2wi1(u,v)+1]m=1nwi1(u,v)+n2δi1(s,v)+|V|1.

On the other hand, we also have

δi(s,v)=m=1nwi(vm1,vm)m=1n2wi1(vm1,vm)2δi1(s,v).

d. Note that every quantity in the definition of w^i is an integer, so w^i is clearly an integer. Since wi(u,v)2wi1(u,v), it will suffice to show that wi1(u,v)+δi1(s,u)δi1(s,v) to prove nonnegativity. This follows immediately from the triangle inequality.

e. First note that s=v0,v1,,vn=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

δ^i(s,v)=m=1nwi(vm1,vm)+2δi1(s,vm1)2δi1(s,vm)=m=1nwi(vm1,vm)2δi1(s,vn)=δi(s,v)2δi1(s,v).

f. By part (a) we can compute δ^i(s,v) for all vV in O(E) time. If we have already computed δi1 then we can compute δi in O(E) time. Since we can compute δ1 in O(E) by part b, we can compute δi from scratch in O(iE) time. Thus, we can compute δ=δk in O(Ek)=O(ElgW) time.


0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn