Why is the direct road not the fastest route?
Network flow and min-cut (topic 06), its special case the transportation problem (18), which keeps only two flat layers of nodes, matching and assignment (07), and shortest paths with dynamic programming (08): the structure real shipping, scheduling and routing problems have.
Bellman's principle of optimality is one line and it powers an enormous amount of the modern world: the tail of an optimal plan is itself optimal.
If the best route from Delhi to Chennai happens to pass through Nagpur, then the portion from Nagpur to Chennai must be the best route from Nagpur to Chennai. If it weren't, you could swap in the better one and improve a route you already called best: a contradiction.
This is what lets you solve a huge problem by solving small ones once each and remembering the answers. You never re-derive "best route from Nagpur"; you look it up. The difference between exponential and linear is nothing more than that bookkeeping.
It also explains the figure's little sting. There is a direct road from S to B, and it is a trap. Optimisation routinely discards the obvious option, which is precisely why humans doing this by intuition leave money on the table so reliably.
The Bellman equation for shortest paths: a recursive definition that is also, read the other way, an algorithm:
d(s) = 0
d(v) = min over edges (u,v) of [ d(u) + w(u,v) ]
Solve it and you get every distance at once. Three standard ways, each with a different assumption:
Dijkstra (1959), O(E + V log V) with a Fibonacci heap (O((V + E) log V) with an ordinary binary one, which is what most implementations actually use) requires all weights ≥ 0. It settles nodes in increasing distance order, which is only valid if edges cannot reduce a distance you have already finalised. Bellman–Ford, O(VE), tolerates negative weights and detects negative cycles, if a distance is still improving after V−1 passes, a negative cycle exists. Floyd–Warshall, O(V³), gives all pairs at once in three nested loops.
The reach of this idea is much wider than roads. The same recursion is Viterbi decoding in communications, sequence alignment in genomics, optimal inventory policy in supply chains, and (with an expectation where the min is) the Bellman optimality equation at the heart of reinforcement learning. Q-learning is this equation solved by sampling. The bridge from operations research into modern AI runs directly through this box.
The map on your phone Every routing request is a shortest-path problem, though not a naive one: continental road networks are far too large for plain Dijkstra at interactive speed, so production systems precompute hierarchies and landmarks that let a query skip most of the graph. The objective is rarely pure distance either: it is a weighted blend of time, turns, tolls and live traffic, which is the same modelling judgement call from topic 01 showing up again.
And in reinforcement learning The same equation, with uncertainty added, is what an RL agent is solving. Including the agents now being used to keep quantum processors calibrated.
Check yourself
What does Bellman's principle of optimality say?
If the best route to Chennai passes through Nagpur, the Nagpur-to-Chennai part must be the best route from Nagpur, or you could swap in a better one. That lets you solve small problems once and look them up.