Dijkstra\'s shortest paths algorithm is executed on the graph above, starting at
ID: 659330 • Letter: D
Question
Dijkstra's shortest paths algorithm is executed on the graph above, starting at A. Assume that vertices A,B,C,D,E are given numbers 0,1,2,3,4 respectively in the implementation. Trace the execution of the algorithm as follows: at the end of every step, show the distance array and the fringe (see table below). The fringe is sorted in a min-heap, in which distance updates can be made, part from delete min, and insert. To show the fringe, draw the binary tree heap structure, with (vertex name,distance) information at each node. Every time there is a change to the heap, show the number of item-to-item comparision needed to make that change, and also what operation resulted in that change. (Ignore the time neede to locate an item in the heap for a distance update.) The worst case running time of Dijsktra's algorithm is O((n + e)log n), on a graph with n vertices and e edges, provided the fringe is stored in a min-heap with O(log n) insert, delete min, and update operations, and the graph is stored in adjacency linked lists. Assume that the graph is stored in an adjacency matrix instead, without changing any other data structure. State clearly which step of the algorithm would be impacted by this change, describe how it would be impacted, and drive the new running time. You don't have to derive the time for the other, non-impacted steps, but you must state all the steps, and write down their big O running times, then sum to single big O.Explanation / Answer
Hi , Sorry but the first question is not clearly visible can you repost it.