Yens improvement to Bellman-Ford Suppose that we order the

Chapter 24, Problem 24-1

(choose chapter or problem)

Yens improvement to Bellman-Ford Suppose that we order the edge relaxations in each pass of the Bellman-Ford algorithm as follows. Before the first pass, we assign an arbitrary linear order 1; 2;:::;jV j to the vertices of the input graph G D .V; E/. Then, we partition the edge set E into Ef [ Eb, where Ef D f.i; j / 2 E W ij g. (Assume that G contains no self-loops, so that every edge is in either Ef or Eb.) Define Gf D .V; Ef / and Gb D .V; Eb/. a. Prove that Gf is acyclic with topological sort h1; 2;:::;jV ji and that Gb is acyclic with topological sort hjV j; jV j1;:::;1i. Suppose that we implement each pass of the Bellman-Ford algorithm in the following way. We visit each vertex in the order 1; 2;:::;jV j, relaxing edges of Ef that leave the vertex. We then visit each vertex in the order jV j; jV j1;:::;1, relaxing edges of Eb that leave the vertex. b. Prove that with this scheme, if G contains no negative-weight cycles that are reachable from the source vertex s, then after only djV j =2e passes over the edges, :d D .s; / for all vertices 2 V . c. Does this scheme improve the asymptotic running time of the Bellman-Ford algorithm?