Describe a modified version of Dijkstras shortest paths algorithm that, in addition to giving the length of the shortest path from s to each vertex v, also gives, for each vertex v, a Boolean flag that is true if and only if the shortest path to v is unique. Analyze your algorithm and give its asymptotic worst-case running time using the appropriate efficient data structures. For example, in the graph pictured below, there are unique shortest paths to vertices s, v, w, and y. Vertex x has two shortest paths: svx and swx. Both of these paths are subpaths of shortest paths to z. However, the path svy is the unique shortest path to y.

Problem 2: Algorithm to determine uniqueness of shortest paths. Describe a modified version of Dijkstra's shortest paths algorithm that, in addition to giving the length of the shortest path from s to each vertex v, also gives, for each vertex v, a Boolean flag that is true if and only if the shortest path to v is unique. Analyze your algorithm and give its asymptotic worst-case running time using the appropriate efficient data structures. For example, in the graph pictured below, there are unique shortest paths to vertices s, v, w, and y. Vertex x has two shortest paths: svx and swx. Both of these paths are subpaths of shortest paths to z. However, the path svy is the unique shortest path to y 2 2 2