Dijkstra’s algorithm is a simple technique for finding the minimum path through a graph with edges and weights.
problem: You will be given a graph with weight for each edge, source vertex and you need to find the minimum distance from the source vertex to rest of the vertices.
Note: This blog explains the algorithm and also guides you on how to implement the algorithm in any language. This blog assumes that you have an idea on graphs.
assume that we have above undirected graph and source is 1. Our goal is to find shortest path from source vertex to every other vertex, i.e., path that has less cost(sum of all weights of edges in the path). For example, one possible path from 1 to 5 will be 3 (2+1).
How it works
first, assume that distance from the source vertex to every other vertex is infinity.
vertices = [1,2,3,4,5]
distances = [0,inf,inf,inf,inf]
select a vertex
comapare distance from source to vertex to the current distance of the vertex, if it is greater than present distance leave otherwise update the distance.
Then the adjacent vertex as visited
After all adjacent vertices are completed, select a vertex from visited with less distance and repeat the process for all the vertices
After all, vertices are completed you will get an output of minimum distance from the source vertex to all other vertices if a path exists.
Time complexity
Dijkstra’s shortest path algorithm is O(E log V) where:
E- no of edges
V- no of vertices
Space complexity: O(|V|)
you can find implementation of Dijkstra's algorithm in my github.
