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!

  • 1
    $\begingroup$ 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. $\endgroup$ – Levent May 21 at 13:57
  • $\begingroup$ so the problem is to select a rooted tree? Or why does the weight in the vertex are important? $\endgroup$ – Phicar May 21 at 13:57
  • $\begingroup$ 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. $\endgroup$ – Yorch May 21 at 13:58
  • $\begingroup$ 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 $\endgroup$ – ADbeat May 21 at 14:07

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.