Designing an algorithm (Dijkstra's adaptative). Thank you!

Problem 1. Unique shortest paths ( 10 points) Although we typically speak of "the" shortest path between two nodes, a single graph could contain several minimum-length paths with the same endpoints. In this problem you will identify nodes that have multiple shortest paths from the source. The input to your algorithm is the adjacency list of the weighted graph G and a source node s. We is such that it only has positive edge weights. In this problem you will most likely apply a slight modification to Dijkstra's and/or call it as a subroutine. Note that in this case you don't have to write out the whole algorithm, rather specify what the modification is, or what the input and output is in case of the subroutine. You can also reference its correctness and running time when appropriate. Specifically, for correctness you can state that the shortest paths tree, i.e. parents list, returned by Dijkstra's indeed consists of shortest paths from s to each node. You do need to prove why the modifications solve the problem. 1. (not to be handed in) Draw some directed weighted graphs for yourself and identify the nodes that have multiple shortest paths from the source. Try to come up with ex 2. Design an algorithm that takes as input G and s and returns a hash table Unique that contains for every node v True/False whether there is a unique shortest path from s to v. 3. Now somebody has already run Dijkstra's algorithm for you on G and gave you the output of it (refer to slides 30 and 36 from March 2nd) d, parents =Dijkstra(G,s) Further, they told you that the node with id x is known to have multiple shortest paths from s to x. Design an algorithm that takes as input G,s,x,d and parents and returns the edges of two different shortest paths from s to x. (If there are more than two, then it doesn't matter which two are being returned.) For full credit your algorithm should run in time O(n+m). Hint: You may want to modify the backtracking algorithm that traces the paths given the parents