Suppose we wish to compute shortest paths in a complete directed graph (a direct
ID: 3843426 • Letter: S
Question
Suppose we wish to compute shortest paths in a complete directed graph (a directed graph in which there exists an edge in each direction between every two vertices), with positive edge weights (so that Dijkstra's algorithm may be used). But rather than using a complicated priority queue data structure, we use an unsorted list L of the vertices that have not yet been processed. That is, the simplified version of Dijkstra's algorithm performs the following steps: initialize the dist and prev information used in the original Dijkstra's algorithm initialize L to be a list of all the vertices in the graph while L is not empty {look at all of the vertices in L to find the vertex v with the minimum value of dist. get(v) remove v from L for each edge v rightarrow w relax(v rightarrow w)} You may assume that looking at all vertices in L takes time proportional to the number of vertices examined, and that removing v from L takes constant time. (a) What is the running time of this algorithm, using O-notation, as a function of the number n of vertices and the number m of edges in the input graph? (b) Would this algorithm be a better or worse choice than the more usual form of Dijkstra's algorithm using a binary heap (whose operations are all O(log n), except for make Queue (), which is O(n) to insert n elements), for this type of graph? Explain your answer.Explanation / Answer
(a). The Dijksatra's algorithm for finding the shortest path, works best when implemented using heap(i.e. priority queue) for whic the running time is O(mLog n) where m is the number of edges and n is the number of vertices.
Another way of finding the shortest path using Dijkastra's Alogirthm is by implementing it without creating a priority queue. In this method a list of the unvisited vertices is created, which is the adjacencey list. The running time of this implementation is O(n2) where n is the number of vertices.
(b). The Dijksatra's algorithm using the binary heap whose running time complexity is O(mLog n) is preffered over other method of implementing it using adjacency list, as it reduces the inputs as well as the time complexity reduces from O(n2) to O(mLog n).