#
Dijkstra's Shortest Path

/********************************************************************* * Author: Isai Damier * Title: Dijkstra's Single Source Shortest Path * Project: geekviewpoint * Package: algorithm.graph * * Statement: * I live in the Bay Area (a.k.a. Silicon Valley). But my parents live * in Boston. Suppose I own a small airplane and know the distance * between all pairs of airports that my plane could reach in one * nonstop flight. How do I find the shortest path from my airport * to my parent's 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. * * Greed as a Virtue: * * Oftentimes, the worst vices sublimate into the greatest virtues. * As shown by the late Professor Edsger Wybe Dijkstra, the best known * solution to this problem is a greedy algorithm. If we call my * starting airport s and my ending airport e, then the intuition * governing Dijkstra's "Single Source Shortest Path" algorithm * goes like this: * * 0] To begin with, my probable itinerary T only contains one airport, * s, since that's where I am starting from: T={s} * 1] Then among all the airports that I could reach from s thru a * nonstop flight, I pick the nearest one (the greedy choice), say * v2. So now T={s,v2}. I also write down some notes next to v2: * the distance from s to v2 and that I went directly from s to v2. * 2] Then among all the airports that I could fly directly into from * either s or v2, I pick the one nearest to s, say w3. Again, I * take some notes next to w3: the distance from s to w3 and whether * I reached w3 from v2 or from s. So now T={s,v2,w3} * 3] Then I repeat the process until my probable itinerary contains e * (i.e. Logan Airport in Boston). As soon as I reach e I can stop * computing. Say T={s,v2,w3,w4,x5,y5,y6,z6,e}. * 4] At this point, to trace out the actual path I am to take, I * backtrack from e to s. Recall that I always took note of how I * reached an airport. So if I reached e from z6, z6 from y5, y5 * from w4, w4 from w3, w3 from s, then to go from s to e I will * travel s -> w3 -> w4 -> y5 -> z6 -> e as my shortest path. * * You probably noticed that v2 and x5 are not on the final path. * That's okay. That's the price for being greedy. But on the bright * side (if you can see it), I know the shortest distance from s to all * the airports that's in T. Hence, not only do I now know the shortest * distance from s to e, I also know the shortest distance from s to z6, * from s to y5, from s to x5, etc. * * Hence in solving for the shortest distance from s to e, * I inadvertently may have solved for the shortest distance to all * the airports in America without any additional effort. I say "may" * because you may choose to halt the search after reaching e. But in * reality Dijkstra's algorithm tend to not supply e as a parameter; * consequently, you normally solve for the distance from s to all * the other vertices. Then you use the result as you wish; say to * find the shortest path to e. Again, there is no additional cost: * Either way, time complexity is O((V+E) log V). * * * Actual Algorithm: * * 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]=100 would mean the distance between s and v is 100. * * 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. Therefore set minDist[s]=0. * * 3] Create a priorityQueue containing all vertices, 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, recalculate the distance from s to x. Note that as long as * a vertex is still on the queue it is effectively not in T * (the probable itinerary), and that by removing a vertex v from the * queue we are essentially adding it to T. * * 6] Re-prioritize the queue based on the recalculated values of minDist. * * 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. * **********************************************************************/ package algorithm.graph; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; public class DijkstraSingleSourceShortestPath { public Integer[][] singleSourceShortestPath(Integer[][] weight,int source){ //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]; Arrays.fill(pred, EVE); Arrays.fill(minDist, INFINITY); //set minDist[source] =0 because source is 0 distance from itself. minDist[source] = 0; PriorityQueue<Integer[]> pq = createPriorityQueue(minDist); while (!pq.isEmpty()) { updatePriorityQueue(pq); int v = pq.remove()[0]; for (Integer[] XD : adjacency(weight, pq, v)) { Integer x = XD[0]; //triangle inequality if (null != x && minDist[x] > minDist[v] + weight[v][x]) { minDist[x] = minDist[v] + weight[v][x]; pred[XD[0]] = v; XD[1] = minDist[x];//update pq. } } } Integer[][] result = {pred, minDist}; return result; } /********************************************************************* * Create a priority queue and load it with the vertices sorted by * minDist. ********************************************************************/ private PriorityQueue<Integer[]> createPriorityQueue(Integer[] dist) { PriorityQueue<Integer[]> pq = new PriorityQueue<Integer[]>(11, new Comparator<Integer[]>() { public int compare(Integer[] A, Integer[] B) { return A[1] < B[1] ? -1 : 1; } }); for (int v = 0; v < dist.length; v++) { pq.add(new Integer[]{v, dist[v]}); } return pq; } /****************************************************************** * 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; } /***************************************************************** * 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()); } }

package algorithm.graph; import org.junit.Test; import static org.junit.Assert.*; public class DijkstraSingleSourceShortestPathTest { /** * Test of singleSourceShortestPath method, * of class DijkstraSingleSourceShortestPath. */ @Test public void testSingleSourceShortestPath() { System.out.println("singleSourceShortestPath"); Integer[][] weight = { {null, 10, null, null, 3}, {null, null, 2, null, 1}, {null, null, null, 7, null}, {null, null, 9, null, null}, {null, 4, 8, 2, null} }; int source = 0; DijkstraSingleSourceShortestPath dijkstra = new DijkstraSingleSourceShortestPath(); Integer[][] expResult = {{-1, 4, 1, 4, 0}, {0, 7, 9, 5, 3}}; Integer[][] result = dijkstra.singleSourceShortestPath(weight, source); assertArrayEquals(expResult, result); weight = new Integer[][]{ {null, 6, 8, 18, null, null}, {null, null, null, null, 11, null}, {null, null, null, 9, null, null}, {null, null, null, null, null, null}, {null, null, null, null, null, 3}, {null, null, 7, 4, null, null},}; expResult = new Integer[][]{{-1, 0, 0, 2, 1, 4}, {0, 6, 8, 17, 17, 20}}; result = dijkstra.singleSourceShortestPath(weight, source); assertArrayEquals(expResult, result); } }