How does Dijkstra's Algorithm work in finding the shortest path in a graph
Dijkstra’s Algorithm
Dijkstra's algorithm, conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later, is a method for determining the shortest paths between nodes in a graph, such as road networks.
Given a source node in the graph, the algorithm calculates the shortest path from that node to every other node. It can also be employed to find the shortest paths from a single starting node to a single destination node by terminating the algorithm once the shortest path to the destination node is found. For instance, if the graph's nodes represent cities and edge path costs denote driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be utilized to discover the shortest route between one city and all other cities.
Dijkstra’s Algorithm:
Step 1: Eliminate all loops (Edges that start and end at the same vertex).
Step 2: Remove all parallel edges between two vertices except the one with the least weight.
Step 3: Create the weight matrix table.
(i) Set 0 to the source vertex and infinity to the remaining vertices.For all vertices, repeat (ii) and (iii).(ii) Identify the smallest unmarked value and mark that vertex.(iii) Determine the vertices directly connected with the marked vertex and update all.Update value formula:
New Destination value = minimum (Old Destination value, Marked value + Edge Weight)
Step 4: Determine the shortest path from source to destination using backtracking.
Place destination vertex in the 'shortest path' list.(i) Set pointer to the last marked value and add that vertex to the 'shortest path' list.(ii) Move the pointer up until the marked value is changed.(iii) If the last marked value has been changed, move the pointer to the marked value in that row and add that vertex to the 'shortest path' list.Repeat (ii) to (iii) until the pointer moves to the source vertex.
Solution:
Step 1: Remove all the loops. (Edges that start and end at the same vertex are called loops)
In the given graph, there are two loops. One is in the vertex C and another one is in the vertex F (starting and ending vertex are same), thus we remove these two edges.
Step 2: Remove all parallel edges between two vertices except the one with the least weight.
In the given graph, there are two edges from vertex A to vertex B, and their costs/weights are 4 and 2. These two edges are called parallel edges. We remove the edge with the higher value (4>2), so we remove the edge with a cost of 4.
Similarly, there is another parallel edge from E to F, and as per the rules, we remove the edge with the higher value (6>3), so we remove the edge with a cost of 6.
Step 3: Create the weight matrix table.
(i) Set 0 to the source vertex and infinity to the remaining vertices.
Weight Matrix Table:-
For all vertices, repeat (ii) and (iii).
(ii) Identify the smallest unmarked value and mark that vertex.
(iii) Find those vertices which are directly connected with the marked vertex and update all.
So, the smallest value in the first row is 0. So we marked 0 and put A as Marked.
Now, find those vertices which are directly connected with A vertex, i.e., B, D, and E.
Now, update B, D, and E.
Update value formula:
New Destination value = minimum (Old Destination value, Marked value + Edge Weight)
New Value of B = minimum (∞, 0+2) = minimum(∞, 2) = 2
New Value of D = minimum (∞, 0+3) = minimum(∞, 3) = 3
New Value of E = minimum (∞, 0+2) = minimum(∞, 2) = 2
The value of all other vertices remains the same. Now the table is:
Now repeat:
The smallest value in the second row is 2. If there are multiple smallest values we can mark any one of them. We marked the first 2 and put B as Marked.
Now, find those vertices which are directly connected with B vertex, i.e., A, D, and C. But A is already Marked, so we will not choose A.
Now, update D and C.
Update value formula:
New Destination value = minimum (Old Destination value, Marked value + Edge Weight)
New Value of D = minimum (3, 2+4) = minimum(3, 6) = 3
New Value of C = minimum (∞, 2+2) = minimum(∞, 4) = 4
The value of all other vertices remains the same. Now the table is:
Now repeat:
The smallest value in the 3rd row is 2. So, we marked the first 2 and put E as Marked.
Now, Find those vertices which are directly connected with the E vertex, i.e., A, and F. But A is already Marked, so we will not choose A.
Now, update F.
Update value formula:
New Destination value = minimum (Old Destination value, Marked value + Edge Weight)
New Value of F = minimum (∞, 2+3) = minimum(∞, 5) = 5
The value of all other vertices remains the same. Now the table is:
Now repeat:
The smallest value in the 4th row is 3. So, we marked the first 3 and put D as Marked.
Now, find those vertices which are directly connected with D vertex, i.e., A, B, C, and F. But A and B are already Marked, so we will not choose A and B.
Now, update C and F.
Update value formula:
New Destination value = minimum (Old Destination value, Marked value + Edge Weight)
New Value of C = minimum (4, 3+2) = minimum(4, 5) = 4
New Value of F = minimum (5, 4+3) = minimum(5, 7) = 5
The value of all other vertices remains the same. Now the table is:
Now repeat:
The smallest value in the 5th row is 4. So, we marked the first 4 and put C as Marked.
Now, find those vertices which are directly connected with the C vertex, i.e., B, D, and F. But B and D are already Marked, so we will not choose B and D.
Now, update F.
Update value formula:
New Destination value = minimum (Old Destination value, Marked value + Edge Weight)
New Value of F = minimum (5, 4+2) = minimum(5, 6) = 5
The value of all other vertices remains the same. Now the table is:
As we see, there is only one unmarked vertex remaining, i.e., F. So, marked 5 and put F as Marked.
So we cover all vertex. Step 3 is over.
Now,
Step 4: Find the shortest path from source to destination using backtracking.
Put destination vertex in ‘shortest path’
(i) Set pointer to the last marked value and put that vertex to the ‘shortest path’ list.
(ii) Move the pointer up until the marked value is changed.
(iii) If the last marked value has been changed then move the pointer to the marked value in that row and put that vertex to the ‘shortest path’ list.
Repeat (ii) to (iii) until the pointer will move to the source vertex.
The last marked value is 5 so put F to the ‘shortest path’ list.
shortest path: F
now, Move the pointer up, the value is the same. So again move the pointer up again, and the value is the same.
So again move the pointer, the value has changed (infinity). So now, move the pointer to the marked value in that row which is 2 and put the vertex E to the ‘shortest path’ list.
shortest path: F -> E
now again, Move the pointer up, the value is the same. So again move the pointer up again, the value has changed (infinity). So now, move the pointer to the marked value in that row which is 0 and put the vertex A to the ‘shortest path’ list.
shortest path: F -> E -> A
So the minimum cost from A to F is: 2 + 3 = 5
