Johnson’s Algorithm for Shortest Path Algorithm
Using Johnson’s algorithm, we can find all pair shortest paths in O(V2log V + VE) time. Johnson’s algorithm uses both Dijkstra and Bellman-Ford as subroutines. If we apply Dijkstra’s Single Source shortest path algorithm for every vertex, considering every vertex as the source, we can find all pair shortest paths in O(V*VLogV) time.
So using Dijkstra’s single-source shortest path seems to be a better option than Floyd Warshall’s Algorithm, but the problem with Dijkstra’s algorithm is, that it doesn’t work for negative weight edge. The idea of Johnson’s algorithm is to re-weight all edges and make them all positive, then apply Dijkstra’s algorithm for every vertex.
Complexity Analysis:
- Time Complexity: O(V^2 * log V + V*E), where V is the number of vertices and E is the number of edges in the graph.
- Auxiliary Space: O(V^2)
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