31,348 views

7 Answers

Best answer
70 votes
70 votes

Answer is A: Queue

We can find single source shortest path in unweighted graph by using Breadth First Search (BFS) algorithm by using "Queue" data structure , in time $O(m+n)$ (i.e. linear with respect to the number of vertices and edges. )

edited by
30 votes
30 votes
Answer(A) The shortest path in an un-weighted graph means the smallest number of edges that must be traversed in order to reach the destination in the graph. This is the same problem as solving the weighted version where all the weights happen to be 1. If we use Queue (FIFO) instead of Priority Queue (Min Heap), we get the shortest path in linear time O(|V| + |E|). Basically we do BFS traversal of the graph to get the shortest paths

Reference: geekforgeeks
5 votes
5 votes

I think none of the answers clearly explains why HEAP is not the correct answer here.

We know that we run “Extract_Min” total |V| time, hence (V logV), but as I see that many have argued that Extract_Min will take O(1) time only since all weights are same. But this is wrong. Had it been Kruskal’s MST algorithm then that argument would have been true. But here we don’t push edge weights in the heap, but rather the distance from the source to any particular vertex, and we know it need not be same for all vertex. And hence it will take O(log V) for both EXTARCT_MIN and RELAX functions.

And hence simple BFS implementation is the only way we can get linear runtime.

edited by
3 votes
3 votes

Ans Can Also be (C) Heap.

  1. Min Heap Creation Time O(V)

  2. Deletion From Heap Constant Time(Because All elements are Equal)

  3. Visiting Adj. List time O(E)

So total is O(V+E)

Answer:

Related questions

90 votes
90 votes
12 answers
1
44 votes
44 votes
4 answers
3
Rucha Shelke asked Sep 26, 2014
53,239 views
The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?$\T...
39 votes
39 votes
4 answers
4
Rucha Shelke asked Sep 17, 2014
25,174 views
Which one of the following in place sorting algorithms needs the minimum number of swaps?Quick sortInsertion sortSelection sortHeap sort