Dijkstra's Algorithm
Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights, producing a shortest path tree. In simpler terms, given a starting node in a graph, the algorithm finds the shortest path from that node to all other nodes in the graph.
Imagine you have a map represented as a graph, where cities are nodes and roads connecting them are edges with associated distances (weights). You want to find the shortest route from your starting city (source node) to every other city on the map. Dijkstra's algorithm will systematically explore the map, always choosing the closest unvisited city, until it has determined the shortest path to every city.The algorithm maintains a set of visited nodes and a set of unvisited nodes. It starts by assigning a tentative distance value to every node: zero for the initial node and infinity for all other nodes. The algorithm then iterates, selecting the unvisited node with the smallest tentative distance, updating the tentative distances of its neighbors, and marking the current node as visited. This process repeats until all nodes have been visited or the target node has been reached. A priority queue is often used to efficiently select the unvisited node with the smallest tentative distance.