# Question: Suppose that we order the edge relaxations in each pass

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?

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?

**View Solution:**## Answer to relevant Questions

Let G be an arbitrary weighted, directed graph with a negative-weight cycle reachable from the source vertex s. Show that an infinite sequence of relaxations of the edges of G can always be constructed such that every ...Suppose that we wish to maintain the transitive closure of a directed graph G = (V, E) as we insert edges into E. That is, after each edge has been inserted, we want to update the transitive closure of the edges inserted so ...Let G = (V, E) be a bipartite graph with vertex partition V = L R, and let G' be its corresponding flow network. Give a good upper bound on the length of any augmenting path found in G' during the execution of ...Prove that the number of comparators in any sorting network is Ω (n lg n).Give a counterexample to the conjecture that if there is a path from u to v in a directed graph G, and if d[u] < d[v] in a depth-first search of G, then v is a descendant of u in the depth-first forest produced.Post your question