Dijkstra with Constraint
by Isai Damier, Android Engineer @ Google

/*********************************************************************
 * Author: Isai Damier
 * Title:  Shortest Path with Constraint
 * Project: geekviewpoint
 * Package: algorithm.graph
 *
 * Statement:
 *   In http://www.geekviewpoint.com/java/graph/dijkstra_shortest_path
 *   we talked about finding the shortest path from my local airport in
 *   Silicon Valley to my parents' airport in Boston, MA. In the
 *   excitement over going to see my parents, I forgot a very important
 *   detail: the landing fee each airport charges. You see, not all
 *   airports charge the same toll. So I can't just blindly pick the
 *   shortest path from Silicon Valley to Boston. I must budget for tolls.
 *   So here is the real problem I actually needed to solve:
 * 
 *     In addition to knowing the distance between all pairs of airports
 *     that my small airplane could reach in one nonstop fight, I also
 *     know how much each airport would charge for toll. So given that
 *     I only have c dollars for toll, what is the shortest path from
 *     my airport to my parents' airport?
 * 
 * Time-complexity: O((V+E) log V)
 *   where V is the number of airports (i.e. vertices/nodes) and E is
 *   the number of paths connecting all of the airports.
 * 
 * Dijkstra Constrained:
 * 
 *  It is highly recommended that you read
 * http://www.geekviewpoint.com/java/graph/dijkstra_shortest_path before
 * proceeding.
 * 
 * ... waiting ... waiting ... waiting ... waiting ... waiting ...
 * 
 * Good. So you got a taste of how life can be when money is not an issue.
 * Now to my problem: How do I factor in my financial limitations?
 * 
 * - Instead of using a vector (i.e. 1D array) to track minDist, we must
 *   now use a matrix (i.e. 2D array), where the rows will represent the
 *   distance from s to the present airport and the columns will
 *   represent money left for the journey.
 * 
 * Actual Algorithm:
 * 
 *  Note: we are still using s as my local airport and e as my parents'
 *        airport in Boston; v can be any airport.
 * 
 *  0] If I am at airport v, then I need to know how I got there and how
 *     far v is from s. Therefore, declare array pred{} to track the
 *     predecessor of v and array minDist to track the distance of v
 *     from s; so that pred[v]=u would mean I got to v from airport u, 
 *     and minDist[v][90]=100 would mean the distance between s and v is
 *     100 miles and I have $90 left in my budget after paying v.
 * 
 *  1] Since we have not done any computation yet, we will fill pred
 *      with -1s and we will fill minDist with infinities. Both meaning
 *     undefined.
 *  
 *  2] Since we are starting at s, we can say that the distance from
 *     where we are to s is zero and that we have not yet spent any money.
 *     Therefore set minDist[s][c]=0.
 * 
 *  3] Create a priorityQueue containing all vertices v, sorted by
 *     minDist; so that vertex s will head the queue since it is the
 *     only vertex with a minDist of zero while all others are infinity.
 * 
 *  4] While queue is not empty, remove the head vertex as v:
 * 
 *  5] For each vertex x that is adjacent to v and that is still on the
 *     queue, if x would not take us over-budget, recalculate the
 *     distance from s to x. To know whether x would take us over-budget,
 *     get the money left after v, say m, and subtract the cost of x
 *     from m: m - cost[x] >= 0. You may want to manually run the
 *     algorithm for a small graph to see how it works.
 * 
 *  6] Re-prioritize the queue based on the recalculated values of
 *     minDist and repeat thru the while-loop.
 * 
 *  After step 6 the computation is done. We are left with two arrays:
 *  pred and minDist. pred tells us the path from s to e, and minDist
 *  tells us the distance along the path. I only care about the path so
 *  I extract the path from pred. But you can do so much more as you wish.
 **********************************************************************/ 
 package algorithm.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class ConstrainedShortestPath {

  public List<Integer> constrainedShortestPath(
          Integer[][] weight,
          int[] cost,
          int money,
          int source,
          int finalDestination)
  {

    //auxiliary constants
    final int SIZE = weight.length;
    final int EVE = -1;//to indicate no predecessor
    final int INFINITY = Integer.MAX_VALUE;

    //declare and initialize pred to EVE and minDist to INFINITY
    Integer[] pred = new Integer[SIZE];
    Integer[][] minDist = new Integer[SIZE][money + 1];
    Arrays.fill(pred, EVE);
    for (Integer[] m : minDist) {
      Arrays.fill(m, INFINITY);
    }

    //set minDist[source][money]=0, as source is 0 distance from itself.
    minDist[source][money] = 0;

    PriorityQueue<Integer[]> pq = createPriorityQueue(money, minDist);

    while (!pq.isEmpty()) {
      updatePriorityQueue(pq);
      int v = pq.remove()[0];
      for (Integer nodeData[] : adjacency(weight, pq, v)) {
        Integer x = nodeData[0];
        if (null == x) {
          continue;
        }

        //find how much landing at v actually cost.
        //If you can't see this, run a small graph manually.
        //Recall that the first v is actuall s with all the money intact.
        int m = -1;
        while (m < money && minDist[v][++m] == Integer.MAX_VALUE);

        //triangle inequality
        int c = m - cost[x];
        if (c >= 0 && minDist[x][c] >(long) minDist[v][m]+weight[v][x]){
          minDist[x][c] = minDist[v][m] + weight[v][x];
          nodeData[1] = minDist[x][c];
          pred[x] = v;
        }
      }
    }

    List<Integer> result = new ArrayList<Integer>();
    int p = finalDestination;
    while (-1 != pred[p]) {
      result.add(p);
      p = pred[p];
    }
    result.add(p);
    Collections.reverse(result);
    return result;
  }//

  private PriorityQueue<Integer[]> createPriorityQueue(
          int money, Integer[][] minDist)
  {
    PriorityQueue<Integer[]> pq = new PriorityQueue<Integer[]>(11,
            new Comparator<Integer[]>() {
              public int compare(Integer[] A, Integer[] B) {
                return A[0] < B[0] ? -1 : 1;
              }
            });
    for (int v = 0; v < minDist.length; v++) {
      pq.add(new Integer[]{v, minDist[v][money]});
    }
    return pq;
  }// createPriorityQueue

  /******************************************************************
   *  Retrieve all the neighbors of vertex v that are
   *  in the priority queue pq.
   *****************************************************************/
  private List<Integer[]> adjacency(Integer[][] G,
          PriorityQueue<Integer[]> pq, int v) {
    List<Integer[]> result = new ArrayList<Integer[]>();
    for (Integer[] ent : pq) {// {u,key[u]}
      int u = ent[0];
      if (G[v][u] != null) {
        result.add(ent);
      }
    }
    return result;
  }// pqNeighbors

  /*****************************************************************
   * Re-prioritize the queue based on changes in the
   *    minDist array.
   *
   * Technical Details: Dijktra's algorithm requires a priority queue
   *    that changes continuously to reflect changes in minDist.
   *    For Java it does not suffice to simply pass new values to
   *    the array objects that constitute the queue. The
   *    PriorityQueue data structure in Java only checks its structure
   *    when it is adding or removing elements. It is unaware of any
   *    direct changes to the objects it comprises. Therefore to force
   *    the queue to re-prioritize, an element is removed and then
   *    immediately added back.
   *
   *****************************************************************/
  private void updatePriorityQueue(PriorityQueue<Integer[]> pq) {
    pq.add(pq.remove());
  }
}// ConstrainedShortestPath
package algorithm.graph;

import static org.junit.Assert.*;

import java.util.Arrays;
import java.util.List;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

public class ConstrainedShortestPathTest {

  ConstrainedShortestPath dijkstra;

  @Before
  public void setUp() throws Exception {
    dijkstra = new ConstrainedShortestPath();
  }

  @After
  public void tearDown() throws Exception {
    dijkstra = null;
  }

  @Test
  public void testConstrainedShortestPath() {
    Integer[][] D = {
      {null, 2, 2, null, null, null, null, null, null, null},
      {null, null, null, 4, null, 16, null, null, null, null},
      {null, null, null, null, 3, null, null, 8, null, null},
      {null, null, null, null, null, null, 4, 4, null, null},
      {null, null, null, null, null, null, null, 4, null, null},
      {null, null, null, null, null, null, null, null, 13, null},
      {null, null, null, null, null, null, null, null, null, 2},
      {null, null, null, null, null, null, null, null, null, 6},
      {null, null, null, null, null, null, null, null, null, 4},
      {null, null, null, null, null, null, null, null, 5, null}};
    int[] S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int money = 199;
    List<Integer> expected = Arrays.asList(0, 1, 5, 8);
    List<Integer> result =
            dijkstra.constrainedShortestPath(D, S, money, 0, 8);
    
    assertEquals(expected,result);
  }
}