Dijkstra with Constraint
by Isai Damier, Android Engineer @ Google

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

  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:

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