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

 Suppose we wish to compute shortest paths in a complete directed

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

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!