Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Differences between Dijkastra and Prim

  1. Dec 14, 2008 #1
    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?
  2. jcsd
  3. Dec 14, 2008 #2
    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.
  4. Dec 31, 2008 #3
    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)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook