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!