Shortest Path Problem Structure¶

Optimal substructure enables shortest path computation: the shortest path to any node consists of shortest paths to intermediate nodes, but negative edges break greedy approaches by invalidating previously optimal choices.

Tension Addressed¶

Generality vs. Efficiency (non-negative edges enable O(E log V); negative edges require O(VE))

Recognizable As¶

Priority-queue-based relaxation (Dijkstra) vs. iterative relaxation (Bellman-Ford); detecting negative cycles.

Canonical Sources¶

Dijkstra, "A Note on Two Problems in Connexion with Graphs," 1959; Bellman, "On a Routing Problem," 1958

Transfers To¶

Network routing (OSPF, BGP), GPS navigation, arbitrage detection, project scheduling, game AI pathfinding

The distinction between Dijkstra and Bellman-Ford illustrates how problem constraints (non-negative vs. any weights) fundamentally change algorithmic possibilities.