Dijkstra's Shortest Path
by Isai Damier

/*********************************************************************
 * 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);
  }
}
Phuzz! Turn your photo into a puzzle!