Greedy Method Algorithm

Question

Single source shortest path problems can be implemented by greedy algorithms using

A. Singly linked list
B.  Min heap
C.  AVL tree
D.  All of the above

Comments

D)...

---

As option is D) lets consider the efficient one , it will be done either by using Dijkstra or Bellman, as we know that Dijkstra is better (though it cant handle the negative weight cycle),so now in Dijkstra's we keep on choosing the node or vertex with minimum weight --->this operation can be mapped to the extract minimum operation of the min heap which takes O(logn) or O(logv) times and then we are relaxing the edges i.e O(Elogv)...so it is the best option we have.

But the answer is D) :)

Answer 1

We can use all of the above for single source shortest path but efficiently it will be done by min-heap

Answer 2

option D) is correct ,We can use all of them for single source shortest path.