TopoLogical Sort
Topological sorting can be used as a single source shortest path algorithm for Directed Acyclic Graphs (DAGs). This works because DAGs guarantees the non-existence of negative cycle.
Working: In DAGs the nodes with indegree=0 will act as source node because of their unreachability from all other nodes. These source nodes are then put into a queue and are allowed to run a DFS traversal to the adjacent nodes to calcualte the shortest path for nodes one by one.
Complexity Analysis:
- Time Complexity: O(V+E).
- 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