3) (10 pts) Given the following edge-weighted graph and Bellman-Ford\'s algo- ri

Question

3) (10 pts) Given the following edge-weighted graph and Bellman-Ford's algo- rithm, answer the following questions to find the shortest paths from vertex I to all other nodes topologically sort G dIv- infinity for all v in V for each u in V in topological sort order do for each neighbor v of u do if d[v] > d[u] + w (u, v) a) (5pts) What are the finishing times of all nodes on the graph? Consider alpha- betic order. b) (5pts) List the shortest distance distTo[ul (from the source to u) and par- entlul (i.e., the last stop (node) on the shortest path to node u) for any node u on the graph. The figure already shows the first nodes whose shortest paths are found. distTo(F) 5 parent(F)- A 20 14 10 13 distTo(A)4 parenti(A)-I 16 source 17 19 12

Explanation / Answer

a)Finishing times of all nodes of graph is worst case complexiety of Bellman-Ford algo i.e. O(VE)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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