#
Dijkstra with Constraint

#======================================================================= # Author: Isai Damier # Title: Shortest Path with Constraint # Project: geekviewpoint # Package: algorithm.graph # # Statement: # In http://www.geekviewpoint.com/python/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/python/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. #======================================================================= from sys import maxint from Queue import PriorityQueue class ConstrainedShortestPath( object ): def __init__( self ): ''' Constructor ''' def constrainedShortestPath( self, weight, cost, money, source, destination ): # 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 for m in range( money + 1 )] for v in range( SIZE )] # set minDist[source][money]=0, as source is 0 distance from itself. minDist[source][money] = 0 pq = self.createPriorityQueue( money, minDist ) while not pq.empty(): self.updatePriorityQueue( pq ) # print "LEFT OVER: %s" % pq.queue v = pq.get()[1] for nodeData in self.adjacency( weight, pq, v ): x = nodeData[1] if x is None: 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. m = 0 while m < money and minDist[v][m] == INFINITY: m += 1 # triangle inequality c = m - cost[x] if c >= 0 and minDist[x][c] > minDist[v][m] + weight[v][x]: minDist[x][c] = minDist[v][m] + weight[v][x] nodeData[0] = minDist[x][c] pred[x] = v result = [] p = destination while -1 != pred[p]: result.append( p ) p = pred[p] result.append( p ) result.reverse() return result def createPriorityQueue( self, money, minDist ): pq = PriorityQueue( len( minDist ) ) for v in range( len( minDist ) ): pq.put( [minDist[v][money], 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] list( pq.queue ) 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 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.ConstrainedShortestPath import ConstrainedShortestPath class Test( unittest.TestCase ): def testConstrainedShortestPath( self ): dijkstra = ConstrainedShortestPath() D = [ [None, 2, 2, None, None, None, None, None, None, None], [None, None, None, 4, None, 16, None, None, None, None], [None, None, None, None, 3, None, None, 8, None, None], [None, None, None, None, None, None, 4, 4, None, None], [None, None, None, None, None, None, None, 4, None, None], [None, None, None, None, None, None, None, None, 13, None], [None, None, None, None, None, None, None, None, None, 2], [None, None, None, None, None, None, None, None, None, 6], [None, None, None, None, None, None, None, None, None, 4], [None, None, None, None, None, None, None, None, 5, None]] S = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] money = 199 expected = [0, 1, 5, 8] result = dijkstra.constrainedShortestPath( D, S, money, 0, 8 ) self.assertEquals( expected, result )