Dijkstra's Algorithm
Dijkstra's algorithm is used to calculate the shortest path between the one node (our choice) and every other node in the graph.
Let's start the algorithm part-
We have a graph as shown in fig (1.a)
Firstly we have to select one node for example we select node C as our source node.
In the algorithm we will mark every node with its minimum distance to node C.For node C,this distance is 0.For the rest of nodes this distance will be infinity.(Fig 1.b).
Secondly we are having a current node as C.
Now, we check the neighbours of our current node i.e A,B,D in any order.
Suppose we begin with B. We add the minimum distance of the current node in this case it is 0 with the weight of the edge which connects C(current node) and we obtain 0+7=7. We compare distance with the minimum distance of B(infinity) and we find that the minimum b/w infinity and 7 is 7.therefore 7 remains as the minimum distance of B. (Fig 1.c)
Now,let's check neighbour A. We add minimum distance of C, 0 with 1 edge connecting current node i.e. C with A to obtain 1.Now again we compare 1 with the minimum distance of A (infinity) and exchange the infinity with 1 as we know minimum between 1 and infinity is 1. (Fig 1.d)
Repeat the same procedure for D.(Fig 1.e)
Now, we have check for all the neighbours of C.Now mark it as visited.(Fig 1.f)
Now we again select a current node.That node must be unvisited with the smallest minimum distance that is A in this case(Fig 1.g)
Now we repeat the same algorithm. We check the neighbours of our current node ignoring the visited nodes,This means we only check B.
For B,we add 1 with 3 (as discussed above)to obtain 4.We compare that 4 with the minimum distance of B(7) and leave the smallest value i.e. 4.
Then we mark A as visited(Fig 1.h)and need a new current node which is non-visited and also have the minimum current distance.
We repeat the algorithm again.This time,we check B and E(because C is already visited).
For B,we obtain 2+5=7 then we compare 7 with B's minimum distance (4) and leave the smallest value as 4.
For E,we obtain 2+7=9,compare it with minimum distance of E(infinity) and leave the smallest one(9).
We mark D as visited and set our current node to B.
We are almost there.We only need to check E. 4+1=5,which is less than E's minimum distance(9), so we keep 5 as minimum distance.
Now mark B as visited and E as current node.
Almost there. We only need to check E. 4 + 1 = 5, which is less than E's minimum distance (9), so we leave the 5. Then, we mark B as visited and set E as the current node.
E does not have non visited neighbours,so we don't need to check anything.
We mark it as visited.
As there are no unvisited node we are done!
Let's start the algorithm part-
We have a graph as shown in fig (1.a)
Firstly we have to select one node for example we select node C as our source node.
In the algorithm we will mark every node with its minimum distance to node C.For node C,this distance is 0.For the rest of nodes this distance will be infinity.(Fig 1.b).
Secondly we are having a current node as C.
Now, we check the neighbours of our current node i.e A,B,D in any order.
Suppose we begin with B. We add the minimum distance of the current node in this case it is 0 with the weight of the edge which connects C(current node) and we obtain 0+7=7. We compare distance with the minimum distance of B(infinity) and we find that the minimum b/w infinity and 7 is 7.therefore 7 remains as the minimum distance of B. (Fig 1.c)
Now,let's check neighbour A. We add minimum distance of C, 0 with 1 edge connecting current node i.e. C with A to obtain 1.Now again we compare 1 with the minimum distance of A (infinity) and exchange the infinity with 1 as we know minimum between 1 and infinity is 1. (Fig 1.d)
Repeat the same procedure for D.(Fig 1.e)
Now, we have check for all the neighbours of C.Now mark it as visited.(Fig 1.f)
Now we again select a current node.That node must be unvisited with the smallest minimum distance that is A in this case(Fig 1.g)
Now we repeat the same algorithm. We check the neighbours of our current node ignoring the visited nodes,This means we only check B.
For B,we add 1 with 3 (as discussed above)to obtain 4.We compare that 4 with the minimum distance of B(7) and leave the smallest value i.e. 4.
Then we mark A as visited(Fig 1.h)and need a new current node which is non-visited and also have the minimum current distance.
We repeat the algorithm again.This time,we check B and E(because C is already visited).
For B,we obtain 2+5=7 then we compare 7 with B's minimum distance (4) and leave the smallest value as 4.
For E,we obtain 2+7=9,compare it with minimum distance of E(infinity) and leave the smallest one(9).
We mark D as visited and set our current node to B.
We are almost there.We only need to check E. 4+1=5,which is less than E's minimum distance(9), so we keep 5 as minimum distance.
Now mark B as visited and E as current node.
Almost there. We only need to check E. 4 + 1 = 5, which is less than E's minimum distance (9), so we leave the 5. Then, we mark B as visited and set E as the current node.
E does not have non visited neighbours,so we don't need to check anything.
We mark it as visited.
As there are no unvisited node we are done!
 |
| Fig 1.a |
 |
| Fig 1.b |
 |
| Fig 1.c |
 |
| Fig 1.d |
 |
| Fig 1.e |
 |
| Fig 1.f |
 |
| Fig 1.h |
 |
| Fig 1.g |
 |
| Fig 1.i |
 |
| Fig 1.j |
 |
| Fig 1.k |
Comments
Post a Comment