Shortest Path Algorithm using Depth-First Search(DFS)
DFS algorithm recursively explores the adjacent nodes untill it reaches to the depth where no more valid recursive calls are possible.
For DFS to be used as a shortest path algorithm, the graph needs to be acyclic i.e. a TREE, the reason it won’t work for cyclic graphs is because due to cycles, the destination node can have multiple paths from the source node and dfs will not be able to choose the best path.
If there does not exist a path between source node and destination node then we can store -1 as the shortest path between those nodes.
Algorithm:
- Distance of source node to source node is initialized to 0.
- Start the DFS from the source node.
- As we go to a neighbouring nodes we set it’s distance from source node = edge weight + distance of parent node.
- DFS ends when all the leaf nodes are visited.
Complexity Analysis:
- Time Complexity: O(N) where N is the number of nodes in the tree.
- Auxiliary Space: O(N) call stacks in case of skewed tree.
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