What are the differences between the Dijkstra Algorithm and the Uniform Cost Search Algorithm?

The Dijkstra Algorithm and the Uniform Cost Search Algorithm are both popular algorithms used for finding the shortest path in a graph. However, there are some key differences between the two:

1. Objective:
- Dijkstra Algorithm: The main objective of Dijkstra's algorithm is to find the shortest path from a single source node to all other nodes in the graph.
- Uniform Cost Search Algorithm: The objective of the Uniform Cost Search algorithm is to find the shortest path from a single source node to a single destination node.

2. Data Structure:
- Dijkstra Algorithm: Dijkstra's algorithm uses a priority queue (often implemented as a min-heap) to prioritize the nodes to be explored based on their tentative distances from the source node.
- Uniform Cost Search Algorithm: The Uniform Cost Search algorithm also uses a priority queue, but it prioritizes the nodes based on their path costs rather than tentative distances.

3. Edge Weights:
- Dijkstra Algorithm: Dijkstra's algorithm can handle both positive and negative edge weights, as long as there are no negative cycles in the graph. It guarantees the shortest path when all edge weights are non-negative.
- Uniform Cost Search Algorithm: The Uniform Cost Search algorithm can only handle non-negative edge weights. It assumes that all edge weights are non-negative and guarantees the shortest path in such cases.

4. Exploration Order:
- Dijkstra Algorithm: Dijkstra's algorithm explores the nodes in a greedy manner, always selecting the node with the smallest tentative distance from the source node. It continues until all nodes have been explored or the destination node is reached.
- Uniform Cost Search Algorithm: The Uniform Cost Search algorithm explores the nodes based on their path costs. It selects the node with the lowest path cost from the priority queue and expands it. This process continues until the destination node is reached or the priority queue becomes empty.

5. Space Complexity:
- Dijkstra Algorithm: The space complexity of Dijkstra's algorithm is O(V), where V is the number of vertices in the graph. This is because it needs to store the distances and the priority queue.
- Uniform Cost Search Algorithm: The space complexity of the Uniform Cost Search algorithm is also O(V), as it requires storing the path costs and the priority queue.

In summary, the Dijkstra Algorithm is used to find the shortest path from a single source node to all other nodes in the graph, while the Uniform Cost Search Algorithm is used to find the shortest path from a single source node to a single destination node. Dijkstra's algorithm can handle both positive and negative edge weights, while the Uniform Cost Search algorithm can only handle non-negative edge weights. The exploration order and the data structures used in the two algorithms also differ.