Before proceeding, it is recommended to have a brief idea about Adjacency Matrix and BFS

Dijkstra’s algorithm is known as single-source shortest path algorithm. It is used for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by Edsger W. Dijkstra in 1956 and published three years later.

We can find shortest path using Breadth First Search (BFS) searching algorithm. This algorithm works fine, but the problem is, it assumes the cost of traversing each path is same, that means the cost of each edge is same. Dijkstra’s algorithm helps us to find the shortest path where the cost of each path is not the same.

At first we will see, how to modify BFS to write Dijkstra’s algorithm, then we will add priority queue to make it a complete Dijkstra’s algorithm.

Let’s say, the distance of each node from the source is kept in d[] array. As in, d[3] represents that d[3] time is taken to reach node 3 from source. If we don’t know the distance, we will store infinity in d[3]. Also, let cost[u][v] represent the cost of u-v. That means it takes cost[u][v] to go from u node to v node.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/188959f1-e3c4-46ca-b606-7c3f4cd77462/Untitled.png

We need to understand Edge Relaxation. Let’s say, from your house, that is source, it takes 10 minutes to go to place A. And it takes 25 minutes to go to place B. We have,

d[A] = 10
d[B] = 25

Now let’s say it takes 7 minutes to go from place A to place B, that means:

cost[A][B] = 7

Then we can go to place B from source by going to place A from source and then from place A, going to place B, which will take 10 + 7 = 17 minutes, instead of 25 minutes. So,

d[A] + cost[A][B] < d[B]

Then we update,

d[B] = d[A] + cost[A][B]

This is called relaxation. We will go from node u to node v and if d[u] + cost[u][v] < d[v] then we will update d[v] = d[u] + cost[u][v].

In BFS, we didn’t need to visit any node twice. We only checked if a node is visited or not. If it was not visited, we pushed the node in queue, marked it as visited and incremented the distance by 1. In Dijkstra, we can push a node in queue and instead of updating it with visited, we relax or update the new edge. Let’s look at one example:

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/f20c2fd8-5c0f-40e7-b48b-e6de702e4aa4/Untitled.png

Let’s assume, Node 1 is the Source. Then,

d[1] = 0
d[2] = d[3] = d[4] = infinity (or a large value)

We set, d[2], d[3] and d[4] to infinity because we don’t know the distance yet. And the distance of source is of course 0. Now, we go to other nodes from source and if we can update them, then we’ll push them in the queue. Say for example, we’ll traverse edge 1-2. As d[1] + 2 < d[2] which will make d[2] = 2. Similarly, we’ll traverse edge 1-3 which makes d[3] = 5.