Question

To implement Dijkstra's shortest path algorithm on unweighted graphs so that it runs in linear time, then data structure to be used is

• A. Heap
• B. B-Tree
• C. Stack
• D. Queue

Answer 1

The correct option is A Heap

Heap and priority queue are very neat data structure allowing:

• Add an element to heap with an associated priority.
• Remove the element from the heap or priority queue that has the highest priority, and return it.
• Peak at the element with highest priority without removing it. A simple way to implement a heap or priority queue data type is to keep a list of elements, and search through the list for the highest priority which gives O(n) time to implement Dijkstra's shortest path algorithm on unweighted graph.