Dijkstra’s Algorithm for Shortest Path Algorithm
Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a weighted graph by iteratively selecting the node with the smallest tentative distance and updating the distances to its neighbours. It ensures the shortest path is progressively discovered and is based on the principle of greedy optimization.
Algorithm:
- Create a Set sptSet (shortest path tree set) that keeps track of vertices included in the shortest path tree, i.e., whose minimum distance from the source is calculated and finalized. Initially, this set is empty.
- Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign the distance value as 0 for the source vertex so that it is picked first.
- While Set doesn’t include all vertices
- Pick a vertex ‘u‘ that is not there in Set and has a minimum distance value.
- Include ‘u‘ to sptSet.
- Then update the distance value of all adjacent vertices of u.
- To update the distance values, iterate through all adjacent vertices.
- For every adjacent vertex v, if the sum of the distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.
Complexity Analysis:
- Time Complexity: O(E*log(V)), where E is the number of edges and V is the number of vertices in the graph:
- Auxiliary Space: O(V)
Shortest Path Algorithm Tutorial with Problems
In this article, we are going to cover all the commonly used shortest path algorithm while studying Data Structures and Algorithm. These algorithms have various pros and cons over each other depending on the use case of the problem. Also we will analyze these algorithms based on the time and space complexities which are frequently asked in coding interviews.
Table of Content
- Types of Shortest Path Algorithms
- 1. Shortest Path Algorithm using Depth-First Search(DFS
- 2. Breadth-First Search (BFS) for Shortest Path Algorithm
- 3. Multi-Source BFS for Shortest Path Algorithm
- 4. Dijkstra’s Algorithm for Shortest Path Algorithm
- 5. Bellman-Ford algorithm for Shortest Path Algorithm
- 6. TopoLogical Sort
- 7. Floyd-Warshall algorithm for Shortest Path Algorithm
- 8. A* Search Algorithm for Shortest Path Algorithm
- 9. Johnson’s Algorithm for Shortest Path Algorithm
- Complexity Analysis For All Shortest Path Algorithms
- Real World Applications of Shortest Path Algorithms