- Please Answer The One Question With Detailed Explanation Especially Parts A And B Thank You 1 (82.88 KiB) Viewed 9 times
please answer the one question with detailed explanation especially parts a and b thank you:)
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
please answer the one question with detailed explanation especially parts a and b thank you:)
please answer the one question with detailed explanationespecially parts a and b thank you:)
5. (20 Points) Consider the following Dijkstra's algorithm discussed in the class and answer questions given below DIJKSTRA(G, w, s) INIT-SINGLE-SOURCE(G, S = Ø Q = G.V while Q is not empty do // Q is a priority queue which we u = EXTRACT-MIN(Q) 1 2 S=SU {u} for each ve Adj do RELAX(u, v, w //G; directed with nonnegative edge weights S) a) Use the algorithm above to find the shortest path from vertex 5 to all other vertices in the graph given below as using adjacency matrix. First draw the graph for the given matrix and the show each step clearly in finding the shortest path. Value 0 indicate that there is no direct path. 3 4 5 U // initialize with all the nodes in V[G] 6 0 3 1 2 3 4 5 6 08 0 6 0 0009 0 0004 0 0 0 080012 12 0 16 0 0 4 20070 5 b) Now modify the Dijkstra's so that it finds not only shortest paths, but also the compute the length of shortest paths and store them in a suitable data structure. Your data structure should return the shortest path distance from the source to any given node in O(1) time. c) Can we use Dijkstra's algorithm to find the shortest paths in a graph with negative edges? Explain your answer clearly.
5. (20 Points) Consider the following Dijkstra's algorithm discussed in the class and answer questions given below DIJKSTRA(G, w, s) INIT-SINGLE-SOURCE(G, S = Ø Q = G.V while Q is not empty do // Q is a priority queue which we u = EXTRACT-MIN(Q) 1 2 S=SU {u} for each ve Adj do RELAX(u, v, w //G; directed with nonnegative edge weights S) a) Use the algorithm above to find the shortest path from vertex 5 to all other vertices in the graph given below as using adjacency matrix. First draw the graph for the given matrix and the show each step clearly in finding the shortest path. Value 0 indicate that there is no direct path. 3 4 5 U // initialize with all the nodes in V[G] 6 0 3 1 2 3 4 5 6 08 0 6 0 0009 0 0004 0 0 0 080012 12 0 16 0 0 4 20070 5 b) Now modify the Dijkstra's so that it finds not only shortest paths, but also the compute the length of shortest paths and store them in a suitable data structure. Your data structure should return the shortest path distance from the source to any given node in O(1) time. c) Can we use Dijkstra's algorithm to find the shortest paths in a graph with negative edges? Explain your answer clearly.