Do minimum depth, spanning trees algorithms exist?

Question

I'm currently optimizing electrical grid planning and the MST doesn't solve the problem well, because if the connection to the main grid is in a radial point all the power has to flow through one edge and will travel a long "electrical distance" to every consumption point.

The problem I'm looking at could be minimizing the MW*distance or active power moment, but that creates a non-linear problem.

So what I want to find is a minimum spanning tree (not the optimal, just most efficient) that minimizes the maximum electrical distance (distance through the graph) to the tree root.

In this way I just buy longer thinner cables that is a cheaper solution to shorter thicker cables.

Earthwork

Answer 1

In this case, you don't want a minimum spanning tree. You want a shortest path tree, which is a spanning tree minimizing the distance from each point in the graph back to the source node. Any standard shortest-path algorithm can be modified to produce a shortest-path tree. For example, a standard implementation of Dijkstra's algorithm can produce such a tree.

That said... shortest path trees are not guaranteed to be cheap, and it's possible to construct graphs where shortest path trees are significantly more expensive than the corresponding minimum spanning tree. In other words, you might have to pay significantly more money to build a shortest path tree than a minimum-spanning tree.

There has been some research into algorithms for finding spanning trees that are good compromises between an MST (minimum total weight) and shortest-path trees (minimum distances to each node), though unfortunately I can't remember off the top of my head where to look to find this.

Hope this helps!

Alissaalistair

Thanks! Ill be thinking in a mixture bitween shortest path tree and minimum spanning tree. Ill keep you updated with my advances! – Crosscurrent

Prim's algorithm with nondegenerate weights w_e is the limiting case as t goes to infinity of Dijkstra's algorithm with weights exp(w_e * t). – Sonja

Didnt understand what you wrote. Prim+weighted costs + t-> Infinity = Dijkstra? Or the opposite? – Crosscurrent

@GonzaloRamírezSagner Dijkstra converges to Prim as the long edges get disproportionately longer. – Sonja

Answer 2

This looks like it is just minimum spanning tree with some extra conditions. Something like Prim's will work.

give a weight to each node to account for consumption at each point. You should end up with a connection between the central node and each outlying node that has the shortest length while also avoiding sending power through too many different nodes.

Deweese

The thing is that the Powerflow through the edges gives the extra weight to the edges themselve and that cost is a function of the topography used. Ponderating the distances could do the trick, but the "how to ponderate" is the magic. Im currently trying to use the normal MST as a starting point and do some 3 - 5 changes (in each change add one edge and then removing another for keeping the radial property of the tree) in such a way that the distances of the most radial nodes are minimized. – Crosscurrent