Search code examples
algorithmshortest-pathminimum-spanning-tree

Are Prim's and Kruskal's Algorithm, shortest path algorithms?

Can these algorithms come under Dijkshtra's , Bellman-Ford , BFS, DFS algorithms?

Solution

  • I think no, and this is why;

    Prim's and Kruskal's algorithms solve the Minimum Spanning Tree problem, and MST problem is different than Shortest Path problem.

    What is the difference between them?:

    MST: requirement is to reach each vertex once (create graph tree) and total (collective) cost of reaching each vertex is required to be minimum among all possible combinations.

    SP: requirement is to reach destination vertex from source vertex with lowest possible cost (shortest weight). So here we do not worry about reaching each vertex instead only focus on source and destination vertices and thats where lies the difference.