title: Weighted Directed Acyclic Graphs: algorithm to find edge weights such that they define a distance function?
body: <p>I have this technical problem that can be formuated with a Directed Acyclic Graph (DAG).
  Nodes represent events (with unknown timing), with directed edges encoding the relation ship: "I'm younger than you/I happened before you".</p>
  
  <p>I need to estimate edge weights (i.e. "dynamic weights") such that the Weighted DAG (WDAG) implies a distance function on the DAG. In other words the sum of weights for paths between nodes A and B should be equal for all paths.</p>
  
  <p>This is an undetermined problem, even if the weights are integers (same underlying reason that topological sorting is not unique, I suppose). In all generality, the edge weights, which represent timeintervals between nodes/events, are real numbers. Therefore I'm introducing some preset objective function C=J(WDAG) on the weighted DAG, here unspecified.</p>
  
  <p>My question is: is there an algorithm that distributes positive definite weights on the WDAG, subject to the constraint 1) that the weights form a distance function of the DAG and 2) minimizing the objective function cost C.</p>
  
  <p>This seems unrelated to the shortest-path or minimum-spanning-tree problems classically associated to WDAG's. Any ideas to a formal or heuristic solution to the above problem?</p>
  
  <p>Regards,</p>
  
  <p>Stephane</p>