#
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 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 )