2. Jin Yen (1970) proposed an improvement to the Bellman-Ford algo- rithm in whi

Question

2. Jin Yen (1970) proposed an improvement to the Bellman-Ford algo- rithm in which we order the edge relaxations in each of the Bellman Ford algorithm as follows. Let G be a directed graph. Before the first pass, we assign an arbitrary linear order to the vertices of G. Then, we partition the edge set E into EyUE, where E -((vrj) EE:i j). Define G1 = (V, Er) and Gb = (V, E). (a) (10 pts) Prove that both Gs and Gy are acyclic (i.e., contain no directed cycles). Remember that the in a directed graph, edge direction matters. (b) (15 pts) Suppose that, in each pass of the Bellman-Ford algo- rithm, we visit each vertex according to this linear order (i.e., we visit vertex vi before , if i

Explanation / Answer

a) From the definition of Gf, if there is a directed path from u to v in Gf then u < v will hold, since for each edge (a,b) in the path from u to v, a<b. suppose if a cycle exists in the graph and it contains vertices u, v then there is directed path from u to v and also from v to u. this gives us u<v and v<u must hold which is not possible so, there will be no cycles in Gf.

Similar argument holds for Gb also, like if there is path from u to v then u>v holds. So if there is cycle then u>v and v>u must hold which is impossible.

b) For the proof lets understand in each pass what length of shortest paths have been explored and fixed.

Lets arrange all vertices in that linear order, all edges in Gf we call forward edges and all edges in Gb we call backward edges.

One important observation in the algorithm is if a shortest path contains only forward or backward edges then it will be identified in the first pass itself.

Now for shortest paths with combination of forward and backward edges,

Lets say in the prevous pass the shortest path to vertex v is explored till some intermediate vertex x, and the remaining path contains series of forward edges(x to y) and a series of backward edges (y to z) then in the subsequent pass the shortest path till z will be explored, so in each pass the shortest paths exploration advances by atleast 2 edges. Since there cannot be shortest paths of length more than |V|-1, it cannot exceed more than |V|/2 passees.

c)The worst case complexity is not improved as it can still take |V|-1 passes and each pass relaxes |E| edges, so the complexity remains O(|V||E|)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.