Dijkstra’s algorithm solves the single-source shortest-path problem: given a weighted graph and a starting node, it finds the lowest-cost route from that node to every other node. Edsger Dijkstra described it in his 1959 paper “A Note on Two Problems in Connexion with Graphs,” where the second problem he posed was to “find the path of minimum total length between two given nodes.” The method requires that all edge weights be non-negative.
The algorithm works greedily. It keeps a set of nodes whose shortest distance from the source is already known for certain, and repeatedly picks, from the remaining nodes, the one with the smallest tentative distance. When a node is selected, the algorithm relaxes its outgoing edges, updating the tentative distances of its neighbors if a shorter route through the chosen node has been found. Once a node is selected its distance is final, because non-negative weights guarantee no later detour can improve it.
The order in which nodes are finalized makes this a classic greedy procedure: each step commits to the locally cheapest unexplored node and never revisits that decision. Choosing that minimum efficiently is what links the algorithm to the priority-queue data structure, which can return the smallest-distance node quickly and makes large graphs practical to process.
Dijkstra’s algorithm is one of the most widely used algorithms in computing. It underlies route planning in road maps and navigation systems, and it appears in network routing where the cost of a link stands in for distance. It is also the conceptual ancestor of later best-first searches such as A*, which add a heuristic to steer the same kind of expanding search toward a single goal.