Problem 7) (20 points) Motivation: When using navigation system app, we often would like to get the shortest 3 paths from source to destination instead of just the shortest path. This is especially useful when driver would like to avoid highways or toll roads or even prefers a more scenic route. Problem: Given a weighted undirected graph G = (V,E) with no negative weights, find the shortest 3 paths from source s to destination vertex t One algorithm to solve this problem is a modification of Dijkstra's algorithm where we keep a QPaths queue of paths from source to every vertex v (Pv) and for each vertex we maintain property (v.c), the number of paths from s to vertex v. At every iteration, we remove from QPaths the Pu with the shortest distance and then add into QPaths all paths Pi where i is a neighbor of u and update i.c for each of these neighbors Whenever a path removed from QPaths reaches the destination (i.e is a Pt), we add the path to a list of results. Once number of solutions found reaches 3, we quit THREE_SHORTEST_PATHS(G, s, t) //s is the source and t is the destination vertices 1.INITIALIZE_VERTICES(G) 2. Solutions- //Set of solution paths from s to t 3. PsA path from s to s 4. Ps.cost 0 //Cost of this path is zero 5. 6. while QPaths != and I solutions I