I expect the answer for each question will be at least 1 letter page long. You must type the answer in MS word Given a graph G = (V, E) and a root s in V, Bellman-Ford algorithm aims to compute a shortest tree of G with s as the root of the tree. The algorithm is also capable of detecting the existence of a negative-weight cycle in the graph G in a way. In detail, after |V| - 1 iterations, the existence of an edge (v, u) in E such that d[v] > d[u] + w (u, v), implies the existence of a negative-weight cycle. Q2. After each iteration, a node may learn a better path throughout a new path from a neighbor. While even in the worst case, which is a line graph, |V|-1 steps are sufficient to propagate a new shortest path from a node to another node in G. However, such discovery of another better path happening after k iterations may make |V| 1 k steps insufficient to propagate a new shortest path information to the rest of the nodes. (in fact this is sufficient.. why?) In the light of the statement above, explain why after |V|-1 iterations, the algorithm must produce an optimal solution (a shortest path tree rooted at the root).