Dijkstra Vs Prim Algorithm | Graph

Prim Algorithm

Prim’s algorithm constructs a minimum spanning tree for the graph, which is a tree that connects all nodes in the graph and has the least total cost among all trees that connect all the nodes. However, the length of a path between any two nodes in the MST might not be the shortest path between those two nodes in the original graph. MSTs are useful, for example, if you wanted to physically wire up the nodes in the graph to provide electricity to them at the least total cost.

Dijkstra Algorithm

Dijkstra’s algorithm constructs a shortest path tree starting from some source node. A shortest path tree is a tree that connects all nodes in the graph back to the source node and has the property that the length of any path from the source node to any other node in the graph is minimized. This is useful if you wanted to build a road network that made it as efficient as possible for everyone to get to some major important landmark. However, the shortest path tree is not guaranteed to be a minimum spanning tree, and the cost of building such a tree could be much larger than the cost of an MST.

Difference between Dijkstra and Prim Algorithm

1. Dijsktra’s algorithm finds the minimum distance from node i to all nodes (you specify i). So in return you get the minimum distance tree from node i. Prims algorithm gets you the minimum spaning tree for a given graph. A tree that connects all nodes while the sum of all costs is the minimum possible.
2. Prim’s algorithm stores a minimum cost edge whereas Dijkstra’s algorithm stores the total cost from a source vertex to the current vertex.
3. Prim’s algorithm works on undirected graphs only, since the concept of an MST assumes that graphs are inherently undirected. Dijkstra’s algorithm will work fine on directed graphs, since shortest path trees can indeed be directed.
4. Dijkstra’s algorithm does not necessarily yield the correct solution in graphs containing negative edge weights, while Prim’s algorithm can handle this.
5. The shortest path tree is not guaranteed to be a minimum spanning tree, and the cost of building such a tree could be much larger than the cost of an MST. In the below graph, shortest path cost from ‘s’ to ‘t’ is 9, while the MST cost is 10.

      5     5
  s *-----*-----* t
     \         /
       -------
         9

Recap

• Breadth-first search is used to calculate the shortest path for an unweighted graph.
• Dijkstra’s algorithm is used to calculate the shortest path for a weighted graph.
• Dijkstra’s algorithm works when all the weights are positive.
• If you have negative weights, use the Bellman-Ford algorithm.