title: How to minimize total cost of shortest path tree
body: <p>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. </p>
  
  <p>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).</p>
  
  <p>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.</p>
  
  <p>In other words, I want the shortest, shortest-path-trees.</p>
  
  <p>Does this ring any bells with anyone? Can anyone point me to relevant algorithms or analogous applications?</p>
  
  <p>Cheers!</p>