gate cse 2015 set 1 question 43

Question

hey i am trying to solve this question GATE CSE 2015 Set 1 | Question: 43 so what is my doubt is if i take the dijkstras algo for mcst then this is right but when i am trying to solve it with prims algos logic ans is different how i am thinking about prims logic is when i am trying to go from node to different node then i will take the smallest path so the other path need to be only one greater then the current path so according ab=10, cd=3,de=7, so ans will be different but the right ans is 69 tell me if there is anything wrong in my approach

Comments

Let assume, instead of 2, it is 20.

Then as per your logic, will you get ab=10 or 21 ?

---

If you start with A, then you can go either B or C. But as AB is not part of your MST, you will explore C then only think about B.

Similarly,  after ABC, you can't explore D via C as CD is not part of the mst. You must visit E. Then must visit F and then D.

Then E to D is 7

Based on that CD is  16 but not 3.