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.

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!

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.