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 worse 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
#   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 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, recalculate the distance from s to x. Note that as long as
#     a vertex is still in 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.
#=======================================================================
 
 

from sys import maxint
from Queue import PriorityQueue

class DijkstraSingleSourceShortestPath( object ):

  def __init__( self ):
      '''
      Constructor
      '''

  def singleSourceShortestPath( self, weight, source ):
    # auxiliary constants
    SIZE = len( weight )
    EVE = -1 # to indicate no predecessor
    INFINITY = maxint

    # declare and initialize pred to EVE and minDist to INFINITY
    pred = [EVE] * SIZE
    minDist = [INFINITY] * SIZE

    # set minDist[source] =0 because source is 0 distance from itself.
    minDist[source] = 0

    pq = self.createPriorityQueue( minDist )
    while not pq.empty():
      self.updatePriorityQueue( pq )
      v = pq.get()[1]
      for XD in self.adjacency( weight, pq, v ):
        x = XD[1]
        # triangle inequality
        if x is not None and minDist[x] > minDist[v] + weight[v][x]:
          minDist[x] = minDist[v] + weight[v][x]
          pred[x] = v
          XD[0] = minDist[x] # update pq.

    return [pred, minDist]


  #=====================================================================
  # Create a priority queue and load it with the vertices sorted by
  # minDist.
  #=====================================================================
  def createPriorityQueue( self, dist ):
    pq = PriorityQueue( len( dist ) )
    for v in range( len( dist ) ):
      pq.put( [dist[v], v] )

    return pq


  #====================================================================
  # Retrieve all the neighbors of vertex v that are
  # in the priority queue pq.
  #====================================================================
  def adjacency( self, G, pq, v ):
    result = []
    for ent in pq.queue: #  [u,key[u]
      u = ent[1]
      if G[v][u] is not None:
        result.append( 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 Python it does not suffice to simply pass new values to
  #    the array objects that constitute the queue. The
  #    PriorityQueue data structure in Python 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.
  #===================================================================
  def updatePriorityQueue( self, pq ) :
    pq.put( pq.get() )
import unittest
from graph.DijkstraSingleSourceShortestPath import DijkstraSingleSourceShortestPath

class Test( unittest.TestCase ):

  def testSingleSourceShortestPath( self ):
    dijkstra = DijkstraSingleSourceShortestPath()
    weight = [
      [None, 10, None, None, 3],
      [None, None, 2, None, 1],
      [None, None, None, 7, None],
      [None, None, 9, None, None],
      [None, 4, 8, 2, None]
    ]

    source = 0
    expResult = [[-1, 4, 1, 4, 0], [0, 7, 9, 5, 3]]
    result = dijkstra.singleSourceShortestPath( weight, source )
    self.assertEquals( expResult, result )

    weight = [
      [None, 6, 8, 18, None, None],
      [None, None, None, None, 11, None],
      [None, None, None, 9, None, None],
      [None, None, None, None, None, None],
      [None, None, None, None, None, 3],
      [None, None, 7, 4, None, None], ]

    expResult = [[-1, 0, 0, 2, 1, 4], [0, 6, 8, 17, 17, 20]]
    result = dijkstra.singleSourceShortestPath( weight, source )
    self.assertEquals( expResult, result )