Dijkstra's Algorithm - is the one of the most classical algorithm for shortest path finding. If someone has to find the shortest path of a given problem, it's the way to go algorithm.
It's used to find shortest distance of nodes in a graph from the source node. That means it finds shortest distance for each node from the source node.
Here we will use the above graph to demonstrate Dijkstra-s Algorithm - Shortest Path Finding.
Here there are few terms used for the algorithm
Initially everything is started unvisited and we can pick any node in the graph as source node. For convenience we will mark node A source and unvisited as well. Apart from source node other nodes values are marked as infinity.
Here if we visit from A to B we will be counting cost. Here you may also call it distance. So from A to B the cost or distance is 4. In this case, this is also the shortest distance.
Visit node C
Now visit node C becomes interesting. There are two ways to visit node C, we can directly visit node C from A, or first we can visit B and then go to C. Definitely we can see to node C, the shortest path is from A.
This is where Dijkstra-s Algorithm shines and finds the shortest path and update the value. This kind of updating shortest value to a node is called relaxation. Let's get started and find the shortest path for all the nodes.
Relaxation
Here we use a terminology called relaxation, we also say we relax nodes to go to other nodes to find the shortest path. For example, when we go to C node from A through B, we find a distance. So first we relax B and then relax C. But we can also go to C from A directly. So to C is the shortest path is from A. You can also say we have relaxed edge B.
Relaxation is trying different edges to find the shortest path.
Let's find the shortest path
Initially all the vertices are set to infinity except from the source node. In our case this is the first one with value 0.
So initially from A to A path value is 0. So 0 is assigned at the A vertex. From A to B the path value is infinity but the edge value is 4. Do remember the edge value is always assigned randomly from the beginning.
Learn more about edge relaxation here
if ( d[u] + c(u, v) < d[v] ) then
{
d[v] = d[u] + c(u, v)
}
The above is the pseudo code for edge relaxation and updating path value. Here we will understand it by below example
In the above example we have three nodes. And we will see use node A as source node. So from A to A distance is 0, and other node's distance is set to infinity.
From A to B or to C, the shortest edge is 4. So we will go to B first and set the distance as shortest distance. From B we will reach out the neighboring nodes. We have only one node C. So here B is marked as visited. And the total edge distance is 4+5 which 9. So from A to C the distance is 9 if we go through B. C does not have any unvisited nodes.
Now once again from A, we can visit C and but we see that here the edge is 11 which is greater than 9. So the shorted distance would be 9 to C going through B.
Algorithm
Let's see how it all work
Lets assume the below graph as our input with the vertex A being the source.