MODIFY DIJKSTRA'S ALGORITHM

(a) 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: (a) Add every edge by some constant k such that there are no more negative-cost edges (b) 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) 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 (V| log(IVI) E log(V 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) Why does your answer to part (b) apply only to simple graphs? Why is it an inaccurate worst-case bound for non-simple graphs