The shortest-path problem asks for the lowest-cost route between nodes in a graph whose edges carry weights, where weight may stand for distance, time, money, or any additive cost. Edsger Dijkstra framed one version directly in his 1959 paper, posing the task of finding “the path of minimum total length between two given nodes.” Variants include finding the shortest path between one specific pair, from a single source to all nodes, or between every pair of nodes.
When all edge weights are non-negative, Dijkstra’s algorithm solves the single-source version efficiently by greedily finalizing the nearest unvisited node at each step. When some weights can be negative, that greedy assumption breaks down, and the Bellman-Ford approach is used instead: it relaxes all edges repeatedly so that improvements can propagate even through negative-weight edges, and it can also detect negative cycles that would make a shortest path undefined.
When the goal is a single target and a good estimate of remaining distance is available, A* search applies a heuristic to steer exploration toward the goal. The 1968 A* paper by Hart, Nilsson, and Raphael showed that with an admissible heuristic, one that never overestimates remaining cost, this guided search still returns a least-cost path while typically examining far fewer nodes than an undirected search.
Shortest-path computations are everywhere in computing. They drive map and navigation routing, the forwarding decisions of network routers, and movement planning in games and robotics. The choice of algorithm follows from the structure of the problem: non-negative weights point to Dijkstra, possible negative weights to Bellman-Ford, and a single goal with a usable heuristic to A*.