(a) (10pt) Consider what happens when you run Bellman-Ford on the following graph, with the source being A. Use the convention that edges (u,v) are relaxed in lexicographic order, sorting first by u then by v. Fill in the following table with the intermediate distance values of all the nodes at the end of each round. (b) (10pt) What problem occurs when we change the weight of edge (H,A) to 1 ? How can we detect this problem when running Bellman-Ford? (c) (10pt) You are given a weighted directed graph G=(V,E) without negative cycles but possibly with negative lengths. To make your life easier, you can assume that no two edges have the same length. Suppose you are promised that for all vV, a shortest path from s to v has increasing edge weights. Give an algorithm for the single-source shortest path problem in this case. Analyze the running time of your algorithm and explain why it is correct. For full credit, your algorithm should run in time O(n+mlogm). Note that this faster than the Bellman-Ford algorithm