Can we use Easy Queue as a substitute of Precedence queue to implement Dijkstra’s Algorithm?


View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

What’s Dijkstra’s Algorithm?

Dijkstra’s Algorithm is used for locating the shortest path between any two vertices of a graph. It makes use of a precedence queue for locating the shortest path. For extra element, about Dijkstra’s Algorithm, you possibly can consult with this article.

Why Dijkstra’s Algorithm makes use of a Precedence Queue?

We use min heap in Dijkstra’s Algorithm as a result of a node can have a number of weighted edges however for the shortest path, we now have to contemplate the smallest weighted edge related to a node. For this, we use a precedence queue (min-heap) which supplies us the minimal factor on the highest of the precedence queue.

For the implementation of Dijkstra’s Algorithm utilizing Precedence Queue, you possibly can take a look at this GFG Article.

The Time Complexity of Dijkstra’s Algorithm is O((V+E)* logV), right here V = no. of nodes within the graph, E = no. of edges within the graph

Can we use a Queue as a substitute of a Precedence Queue?

The reply to this query is sure, we are able to use a queue as a substitute of Precedence Queue. 

The one distinction between a queue and a precedence queue is that we now have to traverse all related nodes of a present node and discover the minimal amongst them after we use a traditional queue which takes time of O(V). However utilizing the precedence queue we are able to optimize it to O(log V). 

The Time Complexity of Dijkstra’s Algorithm utilizing a regular queue is O(V2).

Leave a Reply