When will Dijkstra's algorithm and Prim's algorithm produce different outputs?

Question

I know the difference between Prim's and Dijkstra's algorithm. The former produces a MST while latter gives shortest path from source to all node. Mathematically, these aren't the same, so we wouldn't always expect the two algorithms to produce the same results.

However, while trying different examples I am getting the same result. The pseudocode for Prim's algorithm and Dijkstra's algorithm also look very similar. Can someone please give me an example where Prim's produces a MST which will not be obtained while solving with Dijkstra's or vice-versa.

Also, according to my knowledge. Both of these algorithm uses following approach. Please correct me if I am wrong:

Find shortest i-j where i from set which has already been included and j from set which hasn't been included yet and then add j to the set.

templatetypedef templatetypedef · Accepted Answer · 2013-10-13T19:50:23

A simple example is a collection of four nodes placed at the corners of a square. Place edges of cost 2 between any two adjacent corners, and place edges of cost 3 running diagonally across the square. Running Dijkstra's algorithm from any corner will pick these edges:

* -- *
| \
|  \
*    *

These are the shortest paths, and the total cost of the edges is 7.

Running Prim's algorithm will pick these edges:

* -- *
| 
|
* -- *

This is an MST (total edge cost is 6), but these aren't shortest paths (the path from the upper-left corner to the lower-right corner has cost 4, but there's a more direct route possible.)

As a challenge: try finding graphs where

Dijkstra's algorithm finds a shortest-path tree that is Ω(n) times heavier than the actual MST, and
Prim's algorithm finds an MST where the paths in the tree are Ω(n) times longer than in a corresponding shortest-path tree.

Prim's and Dijkstra's both choose a node by finding some node not in a set and bringing it into the set, but they differ in how they adjust the distances. In Prim's algorithm, the distances used are always the minimum distance from any node out of the set to any node inside the set. In Dijkstra's algorithm, the distance is the minimum of the following value:

distance(start node, u) + l(u, v)

In other words, Dijkstra's algorithm factors in the distance from the start node to nodes outside the set, while Prim's does not.

Hope this helps!

When will Dijkstra's algorithm and Prim's algorithm produce different outputs?

2 Answers