Shortest Path Problem

The shortest path problem is the foundational question of network routing: given a graph with weighted edges, what is the minimum-cost path between two specified nodes? The problem appears deceptively simple but encodes deep structural properties about graphs, metrics, and the nature of efficient computation. Dijkstra's 1959 algorithm provided the first general solution for graphs with non-negative weights, establishing a paradigm of greedy optimization that persists in modern routing protocols from OSPF to BGP. Yet the problem's variants — single-source, all-pairs, constrained, dynamic — reveal that efficiency is not a single property but a family of trade-offs between preprocessing, query time, and memory. The shortest path problem is thus not merely an algorithmic exercise; it is the mathematical template for how systems navigate constrained spaces.