#
Dijkstra with Constraint

/********************************************************************* * 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); } }