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!
Now that you have stated the problem, yes. You will put the weight of the vertex on the new edge connecting the dummy vertex. This is because perhaps it is cheaper to construct two power plants that construct one powerline. For example, say that you have two islands. Say that it costs 1M for the first one and 1M for the second one. but, perhaps, it costs 1.5M to construct a powerline in between them (perhaps they are far far away). So it is cheaper to construct in each island a power plant.
To do this, you do as the hint, and construct a vertex. This vertex will be like a root where each edge corresponds to construct the powerplant in the island. What this is doing is saying that perhaps it is cheaper to have a bunch of trees (a forest) instead of a tree, because when you select the islands where you are going to construct, then you do not need to connect those islands at all.