I hope you already know about Breadth First Search Algorithm - and even if you don't, you won't have a problem understanding this article. Breadth First Search Algorithm gives us the shortest path in an unweighted graph. However, when the graph is weighted, Breadth First Search Algorithm fails. Here is where Dijkstra's Algorithm comes in. Suppose we have the following graph -
We have to start from the START node and reach the FINISH node. The weights of the edges are given. Let's say the weights are the time it takes for us to cover an edge. So, if the weight of an edge is 2, it means it takes us 2 minutes to cover that edge.
If we run breadth-first search algorithm on the graph, we will get the following result-
According to BFS, the shortest path between START and FINISH takes 7 minutes. However, just by observation, we can see that this is not the case. We can go from START to B in 2 minutes, B to A in 3 minutes and A to FINISH in 6 minutes. Here, the total time taken is 6 minutes. We can see that the Breadth First Algorithm does not work for weighted graphs.
Let's now apply Dijkstra’s Algorithm. This algorithm works in four steps.
Step One: Find the cheapest node. You’re standing at the start, wondering if you should go to node A or node B. How long does it take to get to each node? It takes 6 minutes to get to node A and 2 minutes to get to node B. The rest of the nodes, you don’t know yet. Because you don’t know how long it takes to get to the finish yet, you put down infinity.
Step Two: Node B is the closest node … it’s 2 minutes away. Calculate how long it takes to get to all of node B’s neighbours by following an edge from B. Hey, you just found a shorter path to node A! It used to take 6 minutes to get to node A. But if you go through node B, there’s a path that only takes 5 minutes!
When you find a shorter path for a neighbour of B, update its cost. In this case, you found
• A shorter path to A (down from 6 minutes to 5 minutes)
• A shorter path to the finish (down from infinity to 7 minutes)
Step Three: We repeat the above steps. Find the node that takes the least amount of time
to get to. You’re done with node B, so node A has the next smallest time estimate.
Update the costs for node A’s neighbours.
Woo, it takes 6 minutes to get to the finish now! You’ve run Dijkstra’s algorithm for every node (you don’t need to run it for the finish node). At this point, you know
It takes 2 minutes to get to node B.
It takes 5 minutes to get to node A.
It takes 6 minutes to get to the finish.
Now, we can easily trace the path to the FINISH node.
Please note that Dijkstra’s Algorithm works only on Directed Acyclic Graphs. This algorithm can work on unweighted graphs as well because unweighted graphs are nothing but weighted graphs with 0 as weight for all edges.
Also please note that Dijkstra’s Algorithm cannot work with negative weights. For that, we have another interesting algorithm known as the Bellman-Ford algorithm, which we shall discuss in further articles.