(a) (4 points) Suppose you are given a graph that has negative-cost edges, but no negative-cost cycles. Yotu want to find the shortest path between two points and decide to do so using the following algorithm: i. Add every edge by some constant k such that there are no more negative-cost edges. ii. Run Dijkstra's algorithm to find the shortest path. Unfortunately, this algorithm does not work. Give an example of a graph where this algorithm fails to return the correct answer. Be sure to explain why the algorithm fails on this graph you should need to use at most three or four nodes. (b) (3 points) Suppose we have a version of Dijkstra's algorithm implemented using binary heaps with a Note: your example does not need to be complicated O (log(n)) decreasekey method. As we discussed in lecture, this version of Dijkstra's algorithm will have a worst-case runtime of o (V|log(V) |E|log(jV)) Now, suppose we know we will always run this algorithm on a simple graph. Given this information, rewrite the worst-case runtime of Dijkstra's algorithm so it only uses the variable |VI. Briefly justify your answer (c) (3 points) Why does your answer to part (b) apply only to simple graphs? Why is it an inaccurate worst case bound for non-simple graphs