Consider the following Dijkstras algorithm discussed in the class and answer questions given below

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.

b) Now modify the Dijkstras 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 Dijkstras algorithm to find the shortest paths in a graph with negative edges? Explain your answer clearly.

DUKSTRA(G, w, s) //G: directed with nonnegative edge weights INIT-SINGLE-SOURCE(G, s) Q=G.V // Q is a priority queue which we // initialize with all the nodes in VIG] while Q is not empty do u EXTRACT-MIN(a) for each v e Adj[u] do RELAX(u, v, w