Shortest Path Problem

Shortest Path Problem (SPP) is the problem of finding the path of minimum total edge weight between two nodes on a weighted graph (directed or undirected), in one of three core variants: single-source single-destination (one point-to-point), single-source all-destinations (one source to all targets), or all-pairs (every pair). It is the foundational graph-OR problem; for non-negative edges the canonical solution is the polynomial-time algorithm defined by Dijkstra (1959) in a two-page *Numerische Mathematik* paper (binary heap implementation O((V+E)logV)). For negative edges, Bellman-Ford (Bellman 1958) solves in O(VE) and detects negative cycles. For all-pairs, Floyd-Warshall (Floyd 1962) solves by dynamic programming in O(V³). Ahuja-Magnanti-Orlin (1993) *Network Flows* is the canonical textbook. The most frequently invoked OR algorithm in modern industry — it runs underneath navigation services, mapping services, packet-routing protocols (OSPF), parcel-delivery sequencing, highway route planning; on country-scale road networks, modern preprocessing-based approaches (contraction hierarchies — Geisberger 2008) deliver sub-millisecond query time. TSP (#068) and VRP (#002) call shortest path as a subroutine but are different problems: shortest path is polynomial-time, TSP/VRP are NP-hard.