What is the difference between the Dijkstra Algorithm and the Johnson's Algorithm?

The Dijkstra Algorithm and Johnson's Algorithm are both used to solve the single-source shortest path problem in a weighted graph, but they differ in their approach and the type of graphs they can handle efficiently.

1. Approach:
- Dijkstra Algorithm: It is a greedy algorithm that starts from a given source vertex and iteratively selects the vertex with the minimum distance from the source. It then updates the distances of its neighboring vertices and continues until all vertices have been visited.
- Johnson's Algorithm: It is a combination of the Bellman-Ford algorithm and Dijkstra's algorithm. It first adds a new vertex to the graph and connects it to all other vertices with zero-weight edges. Then, it applies the Bellman-Ford algorithm on this modified graph to find the shortest distances from the new vertex to all other vertices. Finally, it uses these distances to reweight the edges and applies Dijkstra's algorithm for each vertex to find the shortest paths.

2. Graph Types:
- Dijkstra Algorithm: It can handle both directed and undirected graphs with non-negative edge weights. However, it does not work correctly for graphs with negative edge weights.
- Johnson's Algorithm: It can handle graphs with both positive and negative edge weights, including graphs with negative cycles. It is particularly useful for graphs with negative edge weights as it transforms them into non-negative weights using the reweighting step.

3. Time Complexity:
- Dijkstra Algorithm: It has a time complexity of O((V + E) log V) using a binary heap or Fibonacci heap for priority queue implementation, where V is the number of vertices and E is the number of edges.
- Johnson's Algorithm: It has a time complexity of O(V^2 log V + VE) using a binary heap or Fibonacci heap for priority queue implementation, where V is the number of vertices and E is the number of edges. The additional V^2 log V term comes from the Bellman-Ford algorithm used for reweighting.

In summary, the main differences between Dijkstra Algorithm and Johnson's Algorithm lie in their approach, the types of graphs they can handle, and their time complexities. Dijkstra Algorithm is a greedy algorithm for non-negative edge weights, while Johnson's Algorithm combines Bellman-Ford and Dijkstra's algorithms to handle graphs with negative edge weights and negative cycles.