Ohk let me clear, Dijkstra's algorithm is just used to find the single source shortest path in the graph.
In algorithm everytime we just pop out the smallest cost vertex from the data structure and for each adjacent child we just simply update the cost of adjacent child and insert the updated cost again in our data structure and remove the old cost from the data structure.
Hence we need smallest cost from list of cost.
We need erase and insert operation.
So it's best to work on data structure which support all these operation with best complexity , like erasing any element from set of element or inserting or extract min element from list.
Priority_queue is good for all these operation with log n factor, as it was made in the form of tree ( balanced type ) which will be able to do operation with logn complexity,
We can use set data structure, which is also know as balance binary search tree also know as avl tree
which can support operation with log n factor.
Hence all of the above mentioned data structure have same behaviour in all of these operation( insert , erase , update etc )
Not exactly, but almost
AVL tree all operation insert , search , delete in o(log N)
Fibonacci heap delete min in o(log n) , find min in o(1)
So aproximately all have similar complexity, but in case of matrix representation of the graph it will increase the overall complexity because in case of matrix we need more space and more traversal.
While in case of adjacency list , space occupied is equivalent to number of edges that is E , which means less traversal , you can go directly from any node to its any child whithout checking the edge is present or not as in case of adjacency matrix.
In case of Kruskal algorithm, it's just used to find minimum spanning tree of the graph , its a greedy algorithm , but it works,
It required sorting of edges with respect to their cost so if E = number of edges , then sorting take ElogE complexity, but it can be done in linear ( only in case of low cost of edges , so that we can use counting sort like algo )
After that , we can simply step by step adding edges , only when two different nodes belong to different component only.
The merging operation can be done faster in o(logn) complexity , with the help of disjoint set union data structure , which can be implemented in array , where merging required log( n ) complexity , which can also tell whether two nodes present in different component or same component.
So variation is just only improving sorting process or merging process.
Complexity of kruskal : ELogE , ElogV .
Also VlogV ( in case when number of edges are almost linear , very less then N^2 ) N = number of nodes.
