DIJKSTRA'S ALGORITHM
Introduction
Dijkstra's algorithm is used to solve the single source shortest paths problem. For a given source vertex in a connected weighted graph, we need to find the shortest path from source vertex to all other vertices.
It applications in transportation planning and packet routing in communication networks, including the Internet. This algorithm is applicable to undirected and directed graphs with nonnegative weights only.
Working Procedure
-
Let the array D[] store the distances of the path from source
to vertex i. Initially the all will be infinity(or some
maximum number).
Let Q[] be the set of all vertices. - Initially D[0]=0 i.e. the distance of source from source is 0(obviously).
-
Loop until Q is not empty
- Remove the vertex which has minimum distance from source and store it as vertex u.
- For each adjacent vertex v to vertex u, perform relaxation(u,v).
-
Relaxation(u,v):
- Let new distance be the sum of distance from source vertex to u(source -> u) and distance from u to v(u -> v).
- If new distance is less than the distance from source vertex to v then this distance(source -> v) shall be equal to new distance.
Time Complexity: O(E * logV)
Code file
Please open this in your pc or with a compatible app in your mobile.
C++ Implementation for DIJKSTRA'S ALGORITHMThat's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!