May 10, 2019 , , , , ,


Dijkstra's algorithm is used to find the shortest path between source vertex (a) to destination vertex (b).


According to Dijkstra's algorithm, to find the shortest path from source vertex to destination vertex we need to follow the following steps.
Step 1: Remove all the loops
Step 2: Remove all parallel edges between two vertices except the one with least weight.
Step 3: Create the weight matrix table
            i) Set 0 to the source vertex and infinite to the remaining vertices.
                        For all vertices, repeat (ii) and (iii)
            ii) Mark the smallest unmarked value and mark that vertex.
            iii) Find those vertices which are directly connected with marked vertex and update all.
                  Update value formula:
                  New Destination value = Minimum(Old destination value, Marked value + Edge weight)
Step 4: Perform backtrack
Some Examples: 

1. Find shortest path from a to g. 



2. Find shortest path from a to c.