What is the difference between Dijkstra's algorithm and Bellman-Ford algorithm?

Dijkstra's algorithm and Bellman-Ford algorithm are both popular algorithms used for finding the shortest path in a graph. However, there are some key differences between the two algorithms.

1. Approach:
- Dijkstra's algorithm is a greedy algorithm that works by selecting the vertex with the smallest distance from the source vertex at each step. It maintains a priority queue to efficiently select the next vertex to explore.
- Bellman-Ford algorithm, on the other hand, is a dynamic programming algorithm that iteratively relaxes the edges of the graph. It considers all edges in each iteration and updates the distance of each vertex if a shorter path is found.

2. Negative Weighted Edges:
- Dijkstra's algorithm does not work correctly with graphs that contain negative weighted edges. It assumes that all edge weights are non-negative, and if negative weights are present, it may produce incorrect results.
- Bellman-Ford algorithm can handle graphs with negative weighted edges. It is designed to detect negative cycles and can correctly identify if a negative cycle exists in the graph.

3. Time Complexity:
- Dijkstra's algorithm has a time complexity of O((V + E) log V), where V is the number of vertices and E is the number of edges in the graph. This complexity arises due to the use of a priority queue.
- Bellman-Ford algorithm has a time complexity of O(V * E), where V is the number of vertices and E is the number of edges in the graph. It needs to relax all edges V-1 times to find the shortest path.

4. Space Complexity:
- Dijkstra's algorithm requires additional space to store the priority queue, resulting in a space complexity of O(V).
- Bellman-Ford algorithm only requires space to store the graph and the distance array, resulting in a space complexity of O(V).

5. Usage:
- Dijkstra's algorithm is commonly used in scenarios where all edge weights are non-negative, such as finding the shortest path in road networks or computer networks.
- Bellman-Ford algorithm is more versatile and can handle graphs with negative weighted edges. It is often used in scenarios where negative weights are present or when the presence of negative cycles needs to be detected.

In summary, Dijkstra's algorithm is a faster algorithm for finding the shortest path in graphs with non-negative edge weights, while Bellman-Ford algorithm is a more flexible algorithm that can handle graphs with negative weights and detect negative cycles.