Yen"s 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 v1, v2,..., v|v| to the vertices of the input graph G = (V, E). Then, we partition the edge set E into Ef ? Eb, where Ef = {(vi , vj) ? E : i < j} and Eb = {(vi, vj) ? E : i > j}. (Assume that G contains no self-loops, so that every edge is in either Ef or Eb.) Define Gf = (V, Ef) and Gb = (V, Eb).

a. Prove that Gf is acyclic with topological sort ?v1, v2,..., v|V|? and that Gb is acyclic with topological sort ?v|V|, v|V|-1,...,v1?. Suppose that we implement each pass of the Bellman-Ford algorithm in the following way.

We visit each vertex in the order v1, v2,..., v|V|, relaxing edges of Ef that leave the vertex. We then visit each vertex in the order v|V|, v|V|-1,..., v1, 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 ⌈|V | /2⌉ passes over the edges, d[v] = δ(s, v) for all vertices v ? V.

c. Does this scheme improve the asymptotic running time of the Bellman-Ford algorithm?