Kruskal’s, Prim’s and Dijkstra’s algorithms

2 min read

Kruskal’s, prim’s and Dijkstra’s algorithms are from most popular algorithms for finding a minimum cost spanning tree. Whereas Dijkstra’s algorithm is used to find the shortest path between nodes in a graph.

Kruskal’s Algorithm

Kruskal algorithm is used to find minimum cost spanning tree of a graph. This algorithm’s main thing is edge weight. This algorithm uses edge weight to find the minimum cost spanning tree.

Steps:

1. Sort all Edges in ascending order of their weights.
2. Start with an empty spanning tree. with not edges only one vertex.
3. Add edges one by one, in the order of their sorted weights, important: Edges should not form a cycle.
4. Repeat the process until all vertices are covered with edge path. important: Edge should be V-1 (V is vertices).

Time complexity for Kruskal’s algorithm will me O(E log E). E is the number of edge.

Prim’s Algorithm

Prim’s algorithm is also a greedy approach to find minimum cost spanning tree. It works by starting from a single vertex and growing the MST by adding the smallest edge that connects the tree to a new vertex.

Steps:

1. Select a node which is called as arbitrary node and add it to the MST.
2. Find the smallest edge that connects one node to another.
3. Repeat the step until all vertices are included in the MST.

Time complexity for prim’s algorithm will be O(E log V), (E is number of edges and V is number of vertices).

Dijkstra’s Algorithm (For shortest Path, Not MST)

Dijkstra’s algorithm is used to find the shortest path from a starting node to all other nodes in a graph with non-negative weights.

Steps:

1. Initialize the distance of array with infinite distance) and starting vertex should be 0.
2. Place all vertices in a priority queue (min-heap), ordered by their current distance.
3. Repeatedly extract the vertex with the minimum distance, update the distances of its neighbors and push the updated neighbor back into the queue.
4. Repeat until all vertices are get covered.

Time complexity for Dijkstra will be O(E log V) exactly same as prim’s algorithm but the difference is Dijkstra’s algorithm is used for finding shortest path but prim’s algorithm is used to find Minimum spanning Tree (MST).

Thanks for reading my blog and sorry for non being consistent in my blogs because of some exams of mine which are in between but i will be consistent after some days.

Thanks for reading my blog, like and share to your family and friends and comment your advice, opinion or anything you want to say to me Thank you, See you next time.