C.29.1:5.2 - Separate route cost, minimum cost and a relaxation bound

Situation and assumptions. Two routes p and q go from A to B, with costs 1 and 4. A route r goes from B to C, with cost 2. These are the only elementary routes considered, costs add when routes are composed, and initially either p or q may be followed by r. The question is the least cost from A to C.

First examine a coarser, different question: whether A can reach B. Both p and q answer yes. A summary that records only their endpoints can answer this reachability question. It cannot define “the cost of the route” by choosing a representative: choosing p gives 1 and choosing q gives 4.

To answer the least-cost question, construct a different operation. Take the minimum over alternatives, and add the cost of a permitted continuation. In the stated case:

cost(p followed by r) = 1 + 2 = 3
cost(q followed by r) = 4 + 2 = 6

min(1+2,4+2) = min(1,4)+2 = 3.

The equality holds because the same continuation is available after both alternatives and adds the same amount. For arbitrary finite costs a and b and common continuation cost c, adding c preserves their order, so min(a+c,b+c) = min(a,b)+c. This explains why the lower-cost prefix can be retained for this continuation. The source witness p followed by r has cost 3.

Change the compatibility premise. Now r is allowed only after q; taking p consumes a permission needed for r. The two arrivals at B have the same location but different permitted continuations. The allowed complete route is q followed by r, with cost 6.

The arithmetic min(1,4)+2 = 3 still holds. Its use as the attainable minimum fails because its selected prefix p cannot be followed by r. Equality of locations did not preserve route composition.

Repair the state at B by retaining whether the continuation permission remains. Let p arrive at (B,0) and q at (B,1). Only (B,1) has the r transition to C. Minimizing over the allowed complete routes in this expanded account yields 4 + 2 = 6. Returning q followed by r supplies an allowed source witness.

There is also a useful result from the coarser account. If it deliberately ignores the permission restriction, its feasible route set contains the real feasible routes. Costs of retained routes remain unchanged. Its minimum 3 is therefore a lower bound on the true minimum, here 6. The bound rules out a source route costing at most 2. It cannot establish that a source route costing at most 4 exists; that would need an allowed witness.

Returned result. Endpoint reachability, the cost of a selected route and the minimum over compatible routes are different questions. Retain history only insofar as it changes future compatibility or cost. When a coarser account is cheaper to use, its lower bound may still answer the receiving question without constructing the optimal source route.