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 G b = (V, Eb).
a. Prove that Gf is acyclic with topological sort ¬v1, v2,..., v |V|¬ and that G b 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?