Shortest Path Algorithms

Finding the shortest path between two nodes in a graph is a common problem with many applications, from network routing to trip planning. Several algorithms exist, each suited for different types of graphs.

Dijkstra's Algorithm

Dijkstra's algorithm is one of the most famous shortest path algorithms. It finds the shortest path from a single source node to all other nodes in a weighted graph with non-negative edge weights.

The algorithm works as follows:

1. Initialize the distances to all nodes as infinite, except for the source node, which is 0.
2. Use a priority queue to keep track of the next most promising node to visit. Initially, it contains the source node.
3. While the priority queue is not empty, extract the node with the smallest distance.
4. For the current node, consider all of its unvisited neighbors. For each neighbor, calculate the distance from the source. If this new distance is shorter than the previously known distance, update it and add the neighbor to the priority queue.
5. The algorithm finishes when all reachable nodes have been visited.

Dijkstra's algorithm is a greedy algorithm, and its time complexity is typically O(E log V) when implemented with a priority queue.