What is Dijkstra Algorithm
Dijkstra Algorithm is a single source shortest path algorithm. Generally, this algorithm is used to find the non-negative value of edges in a weighted graph. One of the simple applications that the Dijkstra algorithm used to find the minimum value between two nodes for a weighted graph. This algorithm's time complexity differs based on the implementation technique.
Dijkstra Algorithm Time Complexity in a Normal Way
As mentioned above, the time complexity of Dijkstra varies on the implementation method.
First of all, the Dijkstra algorithm will be considered that is implemented in a normal way. So the time complexity of this algorithm will be Big O notation O (n2). In this problem, the input size of nodes and edges with weighted values are the major matters. That is why we have to consider the Big O notation to find the time complexity of the Dijkstra algorithm.
Why the Dijkstra algorithm time complexity is O (n2)? To find the minimum distance between nodes, one's has to traverse the whole graph once and another traverse between nodes for another time for the n length array of nodes. This way, we need to for loops to find out the distance of two nodes in a graph.
for (i=0; i<allnodes.length; i++)
{
for (j=0; j<destinationnodes.length; j++)
{
}
}
Then, the time complexity of the Dijkstra algorithm in a normal way is O(n2).
Dijkstra Algorithm Time Complexity using Library Function
The time complexity of the Dijkstra Algorithm in a normal way is too much. We have to find the optimum solution and find out a time reduction way. We traverse the graph's nodes for the n times in n length. Every time the nodes are visited less than twice. Now the time complexity will be O(n2+m). where m is the ' number of pushing a node '. The m will work like a heap or priority queue.
The time complexity can be more reduceable. Now, if one's use the library function of Priority Queue then the time complexity will reduce to O(m log m) from the O(n2). In this method, we have to make a priority queue data structure using the library function. The data structure of priority queue in c++,
#include<queue>
int main ()
{
queue <int> Q;
int u = Q.fornt();
Q.push(s)
Q.pop;
return 0;
}
The node's value will not be updated without any pushing. At the time of Node's value updated, the node's value with node will be inserted in the priority queue.
Short Note:
Dijkstra Algorithm Time Complexity in a Normal Way: O(n2)
Dijkstra Algorithm Time Complexity using Library Function: O(n2+m)
Dijkstra Algorithm Time Complexity using Library Function: O(m log m)
Read Similar Posts:
3. Insertion Sort Time Complexity