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)

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.

a  social news website  is an  internet  website  that features  user-posted stories. such stories are ranked based on popularity, as voted on by other users of the site or by website administrators. users typically comment online on the news posts and these comments may also be ranked in popularity. since their emergence with the birth of  web 2.0, social news sites have been used to link many types of information, including news, humor, support, and discussion. all such websites allow the users to submit content and each site differs in how the content is moderated. on the  slashdot  and  fark  websites,  administrators  decide which articles are selected for the front page. on  reddit  and  digg, the articles that get the most votes from the community of users will make it to the front page. many social news websites also feature an online comment system, where users discuss the issues raised in an article. some of these sites have also applied their voting system to the comments, so that the most popular comments are displayed first. some social news websites also have a  social networking  function, in that users can set up a user profile and follow other users' online activity on the website.