1

How to apply Dijkstra algorithm for a graph to find the MST in such a way that the resulting tree must have an edge between two given vertices? (ex: MST must include an edge between X and Y)

Thanks

coder9
  • 1,571
  • 1
  • 27
  • 52

1 Answers1

5

Dijkstra's algorithm is for shortest paths (not MST), but something similar to Dijkstra's algorithm, as modified to find a minimum spanning tree, is called Prim's algorithm. Prim's algorithm keeps a tree that grows until it spans the entire graph. The additional constraint introduced here does not pose much difficulty: you just start with X-Y as your tree.

Specifically, given that your MST must include the edge (X,Y) (if there are multiple such edges pick the one of smallest weight), start with your tree having two nodes X and Y and the edge between them. Now at each step pick the smallest edge (u,v) where u is in your tree and v outside, add node v and the edge (u,v) to your tree, and repeat.

ShreevatsaR
  • 38,402
  • 17
  • 102
  • 126
  • +1 for Prim's algorithm, very interesting http://en.wikipedia.org/wiki/Prim%27s_algorithm – Mark Booth Jun 01 '11 at 14:51
  • I can simply do this in Prim's but the problem is with using Dijkstra to find MST with the mentioned constraint – coder9 Jun 02 '11 at 01:06
  • 3
    Dijkstra will not find you a MST. Consider the simple graph with 3 edges, A B costs 4, B C costs 5, and A C costs 7. Dikjstra will always want to pick A B and A C for a shortest path from A C of 7, but a total tree weight of 12. But Prim's will always pick A B and B C, since the total tree weight is 9, even though the shortest path from A to C is also 9. The algorithms are very similar, but I'll never call something that behaves like the later Dijkstra. If this is a homework assignment, maybe the prof just wants you to realize how easy it is to Dijkstra's into Prim's algorith? – Rob Neuhaus Jun 02 '11 at 01:18