Dijkstra's algorithm - Part 3 - Tutorial

Here's Part 1 and Part 2

And now for the third and final part of the tutorial. We'll be implementing the actual algorithm here. But before we get started, let's go over some theory.

Dijkstra's Shortest Path Algorithm, (V - Number of Vertices, E - Number of Edges)

• Applies to both Directed graph and Undirected graphs.
• Greedy Algorithm. Always picks the local minimum to extend it's solution.
• Uses Dynamic Programming. Stores solutions from source to every other vertex on the shortest path to the destination.
• Edges cannot be negative.
• Original Implementation by Dijkstra was O(V²) since it did not use a Minimum Priority Queue. Tarjan & Fredman introduced the modern version of the algorithm using a Fibonacci Heap to pick the vertex closest to the source. The Complexity thus became O(E + V logV). 
• Using a Binary Heap instead of a Fibonacci Heap increases the complexity to  O( (E+V) log V).

Variations. There are two variants of the algorithm, there is a subtle difference between them. The first one, you'll traditionally find in textbooks requires your heap to implement the DECREASE-KEY function to change the priority of an arbitrary vertex. The second variant works by reinserting vertices into the priority queue. In this variant, the queue might have the same node with different distance to the source, which is wasteful of course. Without the function it might cost more in terms of space and performance. But for small graphs, both work more or less the same for Binary Heap/Binomial Heap. If we use a Fibonacci Heap, the first variant is more efficient. Here's a good discussion about the difference on these two variations.

Our pqueue implementation doesn't have the decrease-key method and is also implemented as a Binary Heap, so we'll be using the second variant.

The algorithm begins with a couple of auxiliary data structures which can be implemented by a vanilla dictionary (an array if the vertices are represented as positive integers).

The first is the distance, where distance[v] denotes the minimum distance from src to v.
The second is the previous (or parent), where previous[v] = u, denotes that the predecessor to v on the shortest from src  to v is u. This is required only if you're interested in the path from the source to the destination. Otherwise, the algorithm can work without it.

Initially, distance only has a single entry. distance[src] = 0, which is trivial. previous[src]  is populated  by a sentinel value (like NULL or -1). Since the path starts from src itself!

Here's my humble implementation of the algorithm in Python.

	import pqueue
	def dijkstra(graph,src,dst):
	min_dist = dict() # stores shortest path from src, ie min_dist[u] = w denotes, weight of shortest path (src->u) = w
	prev_vertex = dict() # prev_vertex[u], stores the previous node on the shortest path from src to u
	pq = pqueue.pqueue()
	pq.push( (0, src) )
	min_dist[src] = 0 # distance to source is 0.
	prev_vertex[src] = None # no previous node for src
	while not pq.empty():
	(dist , u ) = pq.pop()
	for (v,w) in graph[u]: #v is adjacent to u, edge weight is w
	if v not in min_dist or w + min_dist[u] < min_dist[v]: # shortest path to v is greater than going through u then v?
	min_dist[v] = w + min_dist[u] # make it the new path
	prev_vertex[v] = u
	pq.push( (min_dist[v], v) )
	if dst not in min_dist: #no path from src to dst
	return None,None
	else:
	path = []
	node = dst
	while node:
	path.append(node)
	node = prev_vertex[node]
	path.reverse()
	return min_dist[dst], path #return cost, path

view raw Dijkstra's shortest path algorithm. hosted with ❤ by GitHub

Let's break it down.

	def dijkstra(graph,src,dst):
	min_dist = dict() # stores shortest path from src, ie min_dist[u] = w denotes, weight of shortest path (src->u) = w
	prev_vertex = dict() # prev_vertex[u], stores the previous node on the shortest path from src to u
	pq = pqueue.pqueue()
	pq.push( (0, src) )
	min_dist[src] = 0 # distance to source is 0.
	prev_vertex[src] = None # no previous node for src

view raw gistfile1.txt hosted with ❤ by GitHub

The first part is the initialization of the Algorithm, I simply add details about the source into the distance and previous dictionary. I proceed to then push a tuple into a minimum priority queue (Part 2). The priority is based on the distance of the vertex from the source. Initially, we're pushing the source itself, therefore (0, src) is our first vertex to be processed.

	while not pq.empty():
	(dist , u ) = pq.pop()
	for (v,w) in graph[u]: #v is adjacent to u, edge weight is w
	if v not in min_dist or w + min_dist[u] < min_dist[v]: # shortest path to v is greater than going through u then v?
	min_dist[v] = w + min_dist[u] # make it the new path
	prev_vertex[v] = u
	pq.push( (min_dist[v], v) )

view raw gistfile1.txt hosted with ❤ by GitHub

This is the main shebang of the algorithm. The while loop keeps processing entries in the priority queue until it's exhausted. With each iteration, new vertices are added to the queue when we find a better a path from source to that vertex. Note, initially we've assumed the distance is infinity effectively, therefore every reachable vertex will be processed at least once. We find the vertex which is closest to the source, say u, at that point of time. We iterate through the adjacent vertices, say v_i and find out if a transit route through u is less costly than a direct route from src to v_i. 

Is cost(src->u->v_i ) < cost(src->v_i)? 

This is essentially, cost(src->u) + cost(u->v_i) < cost(src->v_i)

If it is true for any v_i,  we "relax" that edge. Effectively, routing any transit to v_i through u. We update distance and previous for v_i and also push it into the priority queue for future iterations of the while loop. If we were using the first variant of the algorithm, we'd be using the decrease-key instead of pushing a new entry into the priority queue.

	if dst not in min_dist: #no path from src to dst
	return None,None
	else:
	path = []
	node = dst
	while node:
	path.append(node)
	node = prev_vertex[node]
	path.reverse()
	return min_dist[dst], path #return cost, path

view raw gistfile1.txt hosted with ❤ by GitHub

The final part is to simply backtrack the previous dictionary from the destination back the source. This will essentially give us the shortest path from source to destination in the reverse order.

I'll also post a mirror of the animation for the entire algorithm cycle from Wikipedia here. (incase it's ever taken down.)

Well, That's about it, Dijkstra's Shortest Path algorithm in Python. You'll find all the code relevant to the tutorial over here. Hope you've enjoyed the series and it helped you understand this beautifull algorithm better. Please leave any suggestions/improvements/corrections you have in the comment sections. Cheers!