DijkStra Algorithm

Let’s remind ourself of a very simple yet power full graph algorithm today, the Dijkstra algorithm, which basically answer the question, what’s the shortest distance from all nodes to a final destination in a graph, this is also usually used to just find the singular shortest path from A → Z, which is just a biproduct of the bigger question of all shortest paths 😄

So, how do you do it? What is the idea behind this graph algorithm?
Well the basic premis is that, if you have the shortest path to a node, and you keep path finding, extending from that shortest path, you could never improve on the answer, meaning every node that you get to using the previous shortest, is final.
Say we have A , B, C, D, and we’re trying to find shortest to D, then starting from A, with min distance 0, we could go to B, or C. But we pick B because A-B is shorter than A-C, then, we update the current best path from A to B’s neighbors and keep checking path based on the best one. Here:
So we would keep a priority queue of current path to each no like so, say we’re at A, then the queue would be populated by A’s neighbor [(2,B), (3,C)] (distance, node), then we move to check B (pop) cause B is shorter, then we push next neighbors into the queue, say that B to C is 2, then the queue would be [(3C), (4C), (4D)]. You could see that since we keep track of all the distances and always get the smallest one, we could never randomly get a new path to a previous node (B) that is shorter than the one we already finish checking (A-B), there will never be an (A-C-B) that would be shorter because, if there is, AC has to be shorter than AB, and we would just select it ealier.
This might be a bit confusing, but when you implement the idea and walk through it, this is the feeling of the algorithm. 😊

So now we understand the basic premis, which basically is a greedy BFS that keep extending and exploring to the shortest path neighbor. I will walk through basic implementation of the algorithm.
The algorithm is in reverse, so, we have A as our destination, we would need a priority queue and a min distance dictionary to keep track of the best distance so far.
So start with minDist = {A: 0, … Z: infinity}, queue = [(0, A)]. Notice how we set all the mindistance of all nodes to infinity.
Then we pop the smallest distance (A), then start to explore it’s neighbors.

• If edge from current node (A) to neighbor plus current minDist, is less than the found min distance (minDist[neighbor]), then we push it on to the queue for further exploration
• If not, then that means the current node to neighbor path would just be too long, we’ve already found a better path, so we wont explore it, so no push

Then we repeat until the queue is empty. The loop is essentially:

1. Get current shortest path in queue
2. Update the shorest path to node’s neighbors and add those to queue for exploration
   Every time we pop a node from the queue, that distance IS the shortest path.
   The code looks simply like so

edges = [(node, dist), ...] # each edge has a weight
graph = {node: edges, ...} # this is the adjacency graph
 
destination = n # let's say node n
queue = {(0, n)} # distance 0, node n
dist = {i: math.inf for i in range(n)} # min distance dict
dist[n] = 0
 
# we are assuming this is a priority queue, with ppush, and ppop
while queue:
	d, node = queue.ppop()
	if d != dist[node]: continue # just some optimization, we skip if the poped is not shortest path
	for nei, edge in graph[node]:
		if dist[nei] > edge + d:
			# if the new path is shorter than found path, we add it for further exploration
			dist[nei] = edge + d
			queue.ppush((edge+d, nei))
 
print(dist)
# this will be the final resuling shortest paths

Additionally, if you want to keep the actual nodes list for the shortest path, all you need to do is to keep the previous node that leads to the current node in the dist. So each entry would look like

Node: shortest_distance, previous_node

And we would just need to reversely traverse the node to find the path.
Thanks for reading 🤠