# How to implement Prim's algorithm?

I'm currently studying Prim's Algorithm on Minimum Spanning trees. On the textbook I'm studying from there's an assignment on MSTs. My question is that if we have a tree with weighted edges AND vertices how do we tackle this problem, since Prim's algorithm applies only on edges. There's a suggestion to add a dummy node that connects to all vertices. I understand that since this dummy node connects with all other vertices, the weight on the vertices will be the weight on the new edges connecting the node with the rest of the vertices. What is the reasoning behind it? Do I arbitrarily just transfer the vertex weight on the edges? I'm kinda confused

Thank you!

• I don't think I understood the question correctly. Why does it matter to have weights on vertices? Any spanning tree must contain all vertices so it only matters to minimize the weights of the edges. – Levent May 21 at 13:57
• so the problem is to select a rooted tree? Or why does the weight in the vertex are important? – Phicar May 21 at 13:57
• I think you can just ignore the weights on the vertices, since you need to have all of them you can just add the total vertex weight at the very end. – Yorch May 21 at 13:58
• Well, the textbook assignment is about the construction and distribution of a power grid on n islands. There's a p(x) cost to construct a power plant on island x & a c(x,y) cost to construct a powerline between 2 islands. An island is said to be connected on the grid if it has a power plant built on it, or is connected through a path with an island that has a power plant. We have to connect all n island with minimum cost (initially assuming no island has a power plant on it). There's this suggestion to add this dummy node that is connected with all islands. We have to use Prim's algorithm – ADbeat May 21 at 14:07