How to minimize total cost of shortest path tree

Question

I have a directed acyclic graph with positive edge-weights. It has a single source and a set of targets (vertices furthest from the source). I find the shortest paths from the source to each target. Some of these paths overlap. What I want is a shortest path tree which minimizes the total sum of weights over all edges.

For example, consider two of the targets. Given all edge weights equal, if they share a single shortest path for most of their length, then that is preferable to two mostly non-overlapping shortest paths (fewer edges in the tree equals lower overall cost).

Another example: two paths are non-overlapping for a small part of their length, with high cost for the non-overlapping paths, but low cost for the long shared path (low combined cost). On the other hand, two paths are non-overlapping for most of their length, with low costs for the non-overlapping paths, but high cost for the short shared path (also, low combined cost). There are many combinations. I want to find solutions with the lowest overall cost, given all the shortest paths from source to target.

In other words, I want the shortest, shortest-path-trees.

Does this ring any bells with anyone? Can anyone point me to relevant algorithms or analogous applications?

Cheers!

Answer 1

Edit, prompted by commenter: I do not believe that an MST is sufficient for the solution. As the asker indicated, we do not require the connection of all nodes, merely the "sinks", and there are some clear cases when it is better to use a more expensive edge if that edge is to be "recycled" between two or more paths. It my be possible to apply a modified MST algorithm, but I still do not see it.

However, I have revisited the problem, and I believe my min-flow idea was wrong, but here is a linear programming solution that I hope is more... correct.

• For every edge e, create a variable select_e and constrain it between 0 and 1
• For all sinks j, create a self-edge select_j and set it to 1.
• For every edge, create the following constraint: the sum of the outgoing edges (sans self-loops) is greater than or equal to select_e value of that edge. So if the edge is 1, and it has the outgoing edges , , , then the following constraint is created: select_ + select_ >= select_ (note how the self-loop is not included!)
• However, for the incoming edges to the source s, do not create such a constraint.
• Lastly, the target function is to minimize the sum of the select_e values multiplied by the weight of their corresponding edges.

Reasoning: The self-loop bit is a bit of a hack, just designed to get things going. The idea is that we want to start tracing paths from the sinks to the source, and we do that by "obligating" every edge to then mark a new edge from its outgoing vertex. The obligation stops when they reach the source. We minimize the value of the edges we've selected, and that's it.

Concerns: The neighbor-sum constraints seem to be satisfied via loops and the like. Hopefully clever trimming of the constraints (thus obligating the "right" ones to be selected) is possible, but it may not be. This is still just a starting point, but hopefully a fuller one. Also, this clearly calls for integer linear programming, but there are fast approximators for that. That this calls for integer linear programming, however, tempts me to write this off as NP complete and get the hell out of dodge. :)

As part of the edit, I deleted my thoughts on applying the min-cost-max-flow problem, but here is the wiki link just in case:

http://en.wikipedia.org/wiki/Minimum_cost_flow_problem

Answer 2

If you have only positive costs and you are minimizing, just use the Dijkstra's algorithm.

Answer 3

This problem (Steiner Tree) is NP-hard and max SNP-complete, so there are neither polynomial-time algorithms nor PTAS (arbitrarily close approximations) unless P = NP.

The MST can give a weight arbitrarily worse than optimal, unless you know some special feature of your graph (e.g. the graph is planar, or at least that the weights obey the triangle inequality). For example, if you have K_1,000,000,001 with all edge weights 1 and only one target, the optimal solution has weight 1 and the MST has weight 1,000,000,000.

If you assume that all edges between targets and all edges between the source and each target exist, you can still overshoot by an arbitrary factor. Consider the above example, but change the edge weight between the target and source to 2,000,000,000,000,000,000 (you're still off by a factor of a billion from optimal).

Of course you can transform the graph to 'remove' edge weights that are high in time O(E) or so by traversing the graph. This plus a MST of the set of targets and source gives an approximation ratio of 2.

Better approximation ratios exist. Robins & Zelikovsky have a polynomial-time algorithm that is never more than 54.94% worse than optimal: http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf

Chlebik & Chlebikova show that approximating closer than 1.05% is NP-hard: The Steiner tree problem on graphs: Inapproximability results (doi 10.1.1.4.1339)

If your graph is planar, the situation is better. There's a fast algorithm that gives an arbitrarily-close approximation due to Borradaile, Kenyon-Mathieu & Klein (building on Erickson, Monma, & Veinott): An O(nlogn) approximation scheme for Steiner tree in planar graphs (doi 10.1.1.133.4154)