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
with nonnegative integer edge weights . Let . Our goal is to develop an algorithm that runs in 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
be the number of bits in the binary representation of , and for , let . That is, is the "scaled-down" version of given by the most significant bits of . (Thus, for all .) For example, if and , which has the binary representation , then . As another example with , if , then . Let us define as the shortest-path weight from vertex to vertex using weight function . Thus, for all . For a given source vertex , the scaling algorithm first computes the shortest-path weights for all , then computes for all , and so on, until it computes for all . We assume throughout that , and we shall see that computing from takes time, so that the entire algorithm takes time. a. Suppose that for all vertices
, we have . Show that we can compute for all in time. b. Show that we can compute
for all in time. Let us now focus on computing
from . c. Prove that for
, we have either or . Then, prove that for all
. d. Define for
and all , Prove that for
and all , the "reweighted" value of edge is a nonnegative integer. e. Now, define
as the shortest-path weight from to using the weight function . Prove that for and all , and that
. f. Show how to compute
from for all in time, and conclude that we can compute for all in time.
a. We can do this in
b. We can do this in
c. If the
On the other hand, we also have
d. Note that every quantity in the definition of
e. First note that
f. By part (a) we can compute
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供,附加条款亦可能应用