Gabows scaling algorithm for single-source shortest paths

Chapter 24, Problem 24-4

(choose chapter or problem)

Gabows 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 D .V; E/ with nonnegative integer edge weights w. Let W D max.u;/2E fw.u; /g. 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 D dlg.W C 1/e be the number of bits in the binary representation of W , and for i D 1; 2; : : : ; k, let wi.u; / D w.u; /=2ki . That is, wi.u; / is the scaled-down version of w.u; / given by the i most significant bits of w.u; /. (Thus, wk.u; / D w.u; / for all .u; / 2 E.) For example, if k D 5 and w.u; / D 25, which has the binary representation h11001i, then w3.u; / D h110i D 6. As another example with k D 5, if w.u; / D h00100i D 4, then w3.u; / D h001i D 1. Let us define i.u; / as the shortest-path weight from vertex u to vertex using weight function wi. Thus, k.u; / D .u; / for all u; 2 V . For a given source vertex s, the scaling algorithm first computes the shortest-path weights 1.s; / for all 2 V , then computes 2.s; / for all 2 V , and so on, until it computes k.s; / for all 2 V . We assume throughout that jEj jV j 1, and we shall see that computing i from i1 takes O.E/ time, so that the entire algorithm takes O.kE/ D O.E lg W / time. a. Suppose that for all vertices 2 V , we have .s; / jEj. Show that we can compute .s; / for all 2 V in O.E/ time. b. Show that we can compute 1.s; / for all 2 V in O.E/ time. Let us now focus on computing i from i1. c. Prove that for i D 2; 3; : : : ; k, we have either wi.u; / D 2wi1.u; / or wi.u; / D 2wi1.u; / C 1. Then, prove that 2i1.s; / i.s; / 2i1.s; / C jV j 1 for all 2 V . d. Define for i D 2; 3; : : : ; k and all .u; / 2 E, wyi.u; / D wi.u; / C 2i1.s; u/ 2i1.s; / : Prove that for i D 2; 3; : : : ; k and all u; 2 V , the reweighted value wyi.u; / of edge .u; / is a nonnegative integer. e. Now, define yi.s; / as the shortest-path weight from s to using the weight function wyi. Prove that for i D 2; 3; : : : ; k and all 2 V , i.s; / D yi.s; / C 2i1.s; / and that yi.s; / jEj. f. Show how to compute i.s; / from i1.s; / for all 2 V in O.E/ time, and conclude that we can compute .s; / for all 2 V in O.E lg W / time.