Explain Dijkstra's algorithm for finding the shortest path in a graph.

Dijkstra's algorithm is a popular algorithm used to find the shortest path between two nodes in a graph. It works by maintaining a set of unvisited nodes and their tentative distances from the source node. Initially, the distance to the source node is set to 0, and the distances to all other nodes are set to infinity.

The algorithm iteratively selects the node with the smallest tentative distance from the set of unvisited nodes. This node is then marked as visited. For each unvisited neighbor of the selected node, the algorithm calculates the tentative distance by adding the weight of the edge connecting the nodes to the current distance. If this tentative distance is smaller than the current distance of the neighbor, the neighbor's distance is updated.

This process continues until all nodes have been visited or the destination node has been reached. The shortest path can then be reconstructed by backtracking from the destination node to the source node, following the nodes with the smallest distances.

Dijkstra's algorithm guarantees finding the shortest path in a graph with non-negative edge weights. However, it may not work correctly if the graph contains negative edge weights or cycles. In such cases, alternative algorithms like Bellman-Ford or Floyd-Warshall should be used.