title: Dynamic Programming algorithm shortest path between two
body: <p>There's an algorithm currently driving me crazy.</p>
  
  <p>I've seen quite a few variations of it, so I'll just try to explain the easiest one I can think about.</p>
  
  <p>Let's say I have a project P:</p>
  
  <p>Project P is made up of 4 sub projects.</p>
  
  <p>I can solve each of those 4 in two separate ways, and each of those modes has a specific cost and a specific time requirement:</p>
  
  <p>For example (making it up):</p>
  
  <pre><code>P:               1    +    2      +    3     +    4  + .... n
  
  A(T/C)          Ta1/Ca1     Ta2/Ca2  etc      
  
  B(T/C)          Tb1/Cb1 etc
  </code></pre>
  
  <p>Basically I have to find the combination that of those four modes which has the lowest cost. And that's kind of easy, the problem is: the combination has to be lower than specific given time.</p>
  
  <p>In order to find the lowest combination I can easily write something like:</p>
  
  <pre><code>for i = 1 to n
      aa[i] = min(aa[i-1],ba[i-1]) + value(a[i])
      bb[i] = min(bb[i-1],ab[i-1]) + value(b[i])
      ba[i] = min(bb[i-1],ab[i-1]) + value(b[i])
      ab[i] = min(aa[i-1],ba[i-1]) + value(a[i])
  </code></pre>
  
  <p>Now something like is really easy and returns the correct value every time, the lowest at the last circle is gonna be the correct one. </p>
  
  <p>Problem is: if min returns modality that takes the last time, in the end I'll have the fastest procedure no matter the cost.</p>
  
  <p>If if min returns the lowest cost, I'll have the cheapest project no matter the amount of time taken to realize it.</p>
  
  <p>However I need to take both into consideration: I can do it easily with a recursive function with O(2^n) but I can't seem to find a solution with dynamic programming.</p>
  
  <p>Can anyone help me?</p>