Introduction
Dijkstra’s algorithm is one of the most popular algorithms for finding the shortest path between nodes in a graph, which could represent, for example, road networks or communication networks.
It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
How It Works
- Initialize distances from the source to all vertices as infinite, unless they are the source, where it's zero.
- Mark all vertices as unvisited.
- Set the initial node as the current node.
- For the current node, consider all of its unvisited neighbors and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to their current assigned value and update if smaller.
- After considering all neighbors, mark the current node as visited. A visited node will not be checked again.
- If the target node is marked visited or the smallest tentative distance among the vertices in the unchecked set is infinity, stop. The algorithm has finished.
- Otherwise, select the unvisited node that is marked with a tentative distance as the new current node and repeat the process.