title: To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, which data structure should be used?
body: <p>To implement Dijkstra’s shortest path algorithm on <strong>unweighted</strong> graphs so that it runs in linear time, the data structure to be used is:</p>
  
  <ol>
  <li>Queue </li>
  <li>Stack </li>
  <li>Heap </li>
  <li>B-Tree</li>
  </ol>
  
  <p>I found below answers:</p>
  
  <ol>
  <li><p>A Queue because we can find single source shortest path in unweighted graph by using Breadth first search (BFS) algorithm which using "Queue" data structure , which time O(m+n) (i.e. linear with respect to the number of vertices and edges. )</p></li>
  <li><p>A min heap is required to implement it in linear time because if we delete here  a node in min heap it will not take any time in adjustment because all r having same weight so deletion will take O(1) for one node .. so for n-1 node it will be O(n).</p></li>
  </ol>
  
  <p>Can someone explain which one is the correct answer?</p>