title: Difference constraints on Bellman-Ford algorithm
body: <p>Suppose we wanted to use Bellman-Ford to minimize max_i x_i - min_i x_i </p>
  
  <p>over the variables x_1, x_2, ... x_n (total n number of variable) </p>
  
  <p>subject to m constraints of the form x_i - x_j &lt;= c_{i,j} </p>
  
  <p>where c_{i,j} is a specified constant that can be negative. </p>
  
  <p>How can I prove that Bellman-Ford can be used to solve this type of problem in O(n*m) time? </p>
  
  <p>I have tried the following:</p>
  
  <p>create a node i for every variable x_i </p>
  
  <p>make a source node s </p>
  
  <p>create a 0 weight edge from s to all the other nodes</p>
  
  <p>not sure what to do after this... please help, thanks. </p>