Dijkstra's algorithm - Part 2 - Tutorial

For Part 2 of the series, we'll be developing a Priority Queue implemented using a Heap . Continuing from Part 1, we'll be using Python for the implementation.

Fortunately, Python has a PriorityQueue class in the `queue` module. It's more than enough for our purposes, but the Queue module was designed thread safe, so there is a small overhead that comes with it. The Priority Queue is a Minimum Priority Queue by default, it takes in tuples which are compared together to determine their position in the queue. For those unfamiliar with tuple comparison in Python, it works something like this.

>>> (1,2) < (3,4)
True
>>> (1,2) < (1,3)
True
>>> (1,2) < (1,1)
False
>>> (1,2) < (1,2,3)
True
>>> (1,2,3,4) < (1,2,3)
False

The first non equal element  of the both tuples determine the output of the comparison operation. So say you have a bunch of Tasks Ti with Priorities Pi, then we push (Pi, Ti) into the queue, the Queue will automatically order it such that the first element popped will be the one with the lowest priority value.

Here's an example showing this in Action.

	import random,Queue
	pq = Queue.PriorityQueue()
	for q in range(10):
	p = random.randint(0,100)
	print "Inserting %d with priority %d" % (q,p)
	pq.put((p,q))
	while not pq.empty():
	print pq.get()
	raw_input()

view raw PriorityQueue hosted with ❤ by GitHub

Now, what if we wanted the priority queue to work in the reverse order (ie, Largest Value has the higher Priority)? Well, there isn't any feature provided for this by the module, but we can do a clever little hack, observe when we negate the priority the output of the comparison operation flips. Therefore, For a Maximum Priority Queue, simply insert (- Pi, Ti)....and presto, now the elements are ordered by decreasing order of priority.

For the sake of learning, we'll implement our own Priority Queue. Using a heap for a backend implementation. Python comes with the heapq module. The heapq module lets us use a list as a heap, it has the heappush and heappop functions push an element onto a heap. The comparison of the elements work as  before with the Priority Queue.

Here's the class I wrote, it has a priority-tie-breaking mechanism. I simply add a counter as the second element to the tuple, this is essential for two things. One, when two elements have the same priority, the one inserted first will be popped first. Second, if we don't add this, then we'll have to make the data-elements comparable otherwise python will attempt to compare 2 elements (possibly non-comparable) with 2 equal priorities. In order to avoid this, we introduce the counter. So the Tuple Comparison will be resolved at the counter itself. Also, I've abstracted the min/max priority by having the pqueue class take care of negating the priorities. Far more convenient in my opinion.

	import heapq as hp
	class pqueue:
	def __init__(self, minheap = True):
	self.heap = []
	self.mul = 1 if minheap else -1
	self.count = 0
	def size(self):
	return len(self.heap)
	def push(self,item):
	if item and isinstance(item, tuple) and isinstance(item[0],int):
	self.count = self.count + 1
	hp.heappush(self.heap,(item[0] * self.mul,self.count) + item[1:])
	else:
	raise Exception("parameter has to be a tuple with the first entry as an integer.")
	def pop(self):
	if self.empty(): raise Exception("pqueue is empty.")
	item = hp.heappop(self.heap)
	return (self.mul * item[0],) + item[2:]
	def __str__(self):
	return str(list((self.mul * p, r) for p,q,r in self.heap))
	def __repr__(self):
	return str(list((self.mul * p, r) for p,q,r in self.heap))
	def empty(self):
	return len(self.heap) == 0
	def clear(self):
	self.heap = []

view raw pqueue hosted with ❤ by GitHub

Here's the complete source code.

We now have the essential tools for implementing our Dijkstra's Shortest Path algorithm. Until next time...