Let's implement the Dijkstra's algorithm on the below Weighted Directed Graph.
In the above graph S is the source node, Now let's implement Dijkstra's algorithm to find the shortest path.
Let's go through the order of implementation :
1. Initialize-Single-Source(G,s) is executed and all vertices are given initial d and pi values.
2. Queue Q now contains all vertices, S is assigned empty set.
3. Enters while loop
4. Minimum Vertex from the available vertices in Q is assigned to u.
5. d value is updated in Relax function. For d value to be updated the current d value must be greater than the new d value. New d value will be d[u] + w[u,v].
6. Repeat statements 4,5 until Q becomes empty.
The below table represents initial values of all vertices after step 1 and step 2 :
Let's go through the order of implementation :
1. Initialize-Single-Source(G,s) is executed and all vertices are given initial d and pi values.
2. Queue Q now contains all vertices, S is assigned empty set.
3. Enters while loop
4. Minimum Vertex from the available vertices in Q is assigned to u.
5. d value is updated in Relax function. For d value to be updated the current d value must be greater than the new d value. New d value will be d[u] + w[u,v].
6. Repeat statements 4,5 until Q becomes empty.
The below table represents initial values of all vertices after step 1 and step 2 :
The above table represents the values of the graph after the execution of the function Initialize-Single-Source(G,s). And the Queue determines the set Q ( Line 3 ) which is assigned all the vertices in the graph. Also s is added to the empty set S. Now in the while loop, u is assigned to the minimum value among all vertices in Q, s is the vertex with value 0 and all other are infinity, so u is assigned to vertex s.
Now from vertex s there are two outgoing edges ( A and C )
Now from vertex s there are two outgoing edges ( A and C )
For Vertex A Current Value = Infinity New Value = d[u] + w[u,v] = 0 + 10 = 10. Current Value is greater than New value. d[a] is updated to 10. Pi[a] will now be S | For Vertex C Current Value = Infinity New Value = d[u] + w[u,v] = 0 + 5 = 5. Current Value is greater than New value. d[c] is updated to 5. Pi[c] will now be S |
Since Dijkstra's follows the greedy approach we proceed to node with minimum distance and in our case vertex C has the minimum distance ( among remaining vertices A,B,C,D) hence now u will be assigned to vertex C. Vertex C is added to the set S.
Now from C we have 3 outgoing edges ( A, B & D ).
Now from C we have 3 outgoing edges ( A, B & D ).
For Vertex A Current Value = 10 New Value = d[u] + w[u,v] = 5 + 3 = 8. Current Value is greater than New value. d[a] is updated to 8. Pi[a] will now be C | For Vertex B Current Value = infinity New Value = d[u] + w[u,v] = 5 + 9 = 14. Current Value is greater than New value. d[b] is updated to 14. Pi[b] will now be C | For Vertex D Current Value = infinity New Value = d[u] + w[u,v] = 5 + 2 = 7. Current Value is greater than New value. d[d] is updated to 7. Pi[d] will now be C |
We now proceed to node with minimum distance, which right now is vertex D with distance 7 ( among vertices A,B & D). Now u will be assigned to vertex D and D is also added to the set S.
Now from vertex D we have two outgoing edges ( S and B ).
Now from vertex D we have two outgoing edges ( S and B ).
For Vertex S Current Value = 0 New Value = d[u] + w[u,v] = 7 + 7 = 14. Current Value is not greater than New value. d[s] will remain the same. | For Vertex B Current Value = 14 New Value = d[u] + w[u,v] = 7 + 6 = 13. Current Value is greater than New value. d[b] is updated to 13. Pi[b] will now be D |
Now we proceed to vertex A ( least among A and B ). Vertex A is now assigned to u and is also added to set S.
From vertex A we have two outgoing edges ( C and B ). d[c] cannot be updated because it is currently 5 and the new value will be ( 8 + 3 ) 11. Since 5 is less than 11 we cannot update d[c].
d[b] will now be ( 8 + 1 ) 9. Since 13 is greater than 9 it will be updated to 9. Similarly Pi[b] will now be updated to D. The new table will look like :
From vertex A we have two outgoing edges ( C and B ). d[c] cannot be updated because it is currently 5 and the new value will be ( 8 + 3 ) 11. Since 5 is less than 11 we cannot update d[c].
d[b] will now be ( 8 + 1 ) 9. Since 13 is greater than 9 it will be updated to 9. Similarly Pi[b] will now be updated to D. The new table will look like :
For Vertex C Current Value = 5 New Value = d[u] + w[u,v] = 8 + 3 = 11. Current Value is not greater than New value. d[c] will remain the same. | For Vertex B Current Value = 13 New Value = d[u] + w[u,v] = 8 + 1 = 14. Current Value is greater than New value. d[b] will be updated to 9. Pi[b] will be updated to A. |
Now we are only left with vertex B in the queue Q. we proceed to B, from B we have only one outgoing edge (D). D cannot be updated since its current value is not greater than the new value. The final tables will be :
Q is now empty, so the loop terminates.
Q is now empty, so the loop terminates.
Now the shortest path is Starting from S to C then to D via C and then to A via C and then to B via A.