Part 3. (10 points) Modifying Dijkstra's algorithm (a) (4 points) Suppose you are given a graph that has negative-cost edges, but no negative-cost cycles. You 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. Note: your example does not need to be complicated -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 O (log(n)) decreaseKey method. As we discussed in lecture, this version of Dijkstra's algorithm will have a worst-case runtime of O (| log(WI) + El log( VD). 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 |V]. 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