Question

Assume that

No two edges have the same weight
There are no cycles of net negative weight
There are no self-edges (edges leading from a vertex to itself)
There are V vertices and E edges
When I say

"the lightest edge" I mean "the edge with the smallest weight."
"the heaviest edge" I mean "the edge with the largest weight."

Assume in this question that, in addition to the conditions specified at the beginning of the quiz, there are no negative edges, graphs have at least as many edges as vertices, and graphs are represented with a list containing all of the graph's edges. Within the list, each edge is represented with an ordered pair. Assuming that the graph representation is at no point converted to a more efficient form, what is the tightest upper bound that can be put on Dijkstra's algorithm. (Assume that Dijkstra's algorithm uses a binary heap.)?

a. (V^2)
b. (V 2 log E)
c. (E^2log V)
d. (VE)
e. (CV+E) log)
f. (VE log )
g. (E^2)
h. (E log V)

Answer 1

Step-by-step explanation:

Create a min-heap of size v (the number of vertices), each of which contains the vertex number and the distance from the root vertex (which is the source vertex).

So, the distance on the root vertex would be 0. And let the distances on all other nodes be infinite(since they will be updated later).

Until the min-heap gets empty, do the following

(i) Extract that vertex from the min-heap, which has the minimum distance value, using Extract-Min operation, which takes O(logV). Lets name it u

(ii) Now, for every adjacent vertex of u, say v, check if v is in min-heap or not. If yes, and if the distance value of u plus the edge weight u-v is less than the distance value of v, then update the distance value of v.

Running time of O(ElogV) is obtained, as the Extract-Min operation which takes O(logV), is performed at most E times, i.e. the number of edges times.