Differences between Dijkastra and Prim

  • Thread starter Thread starter rootX
  • Start date Start date
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
2 replies · 8K views
rootX
Messages
480
Reaction score
4
I understand both algorithms. But, I was wondering would there be a case where results between Dijkstra and Prim are different? I haven't found an example where this happens.
i.e. Would the path between A and B provided by the minimum spanning tree be always equal to the minimum distance between A and B from Dijkstra?
 
Physics news on Phys.org
If there are two minimum paths, the results could be different using the two different methods. Obviously, if there is only one minimum path with no alternative having the same total weight, they would be identical paths.
 
Nop, the Prim's algorithm only gives the set with minimum weight of edges connecting all nodes.

Imagine this undirected graph:

A-B weight 2
B-C " 2
C-D " 2
A-D " 4

The shortest path from A to D is using the direct edge with cost 4, while the spawning tree uses the other edges (total sum 6)