MATH.20:5.1 - Bound a shortest path before completing a search

Consider a finite directed graph with nonnegative edge weights and at least one path from s to t. Its shortest path length D is attained: cycles can be removed without increasing length, leaving one of finitely many simple paths.

Any particular s-to-t path of length U gives D≤U. For a lower bound, assign a number p(v) to each node such that, for every edge from u to v,

p(v)-p(u)≤w(u,v).

Along any path, add these inequalities. The intermediate potentials cancel, giving p(t)-p(s)≤path length. Therefore p(t)-p(s)≤D≤U.

Take nodes s,a,b,t and these edges:

The path s-a-t gives U=7. Choose p(s)=0, p(a)=2, p(b)=3, p(t)=4. The edge differences are respectively 2,2,3,1,1, each no larger than its edge weight. Thus 4≤D≤7.

The equality cases suggest s-a-b-t. It has length 4, meeting the lower bound, so D=4. The proof of optimality uses a feasible path and the comparison applying to every path; it does not need a list of every possible path.

Changed condition. Add an edge s-to-t of weight 1. The old potential violates its new edge inequality, since 4>1; its lower bound is invalid for the enlarged graph. The old path still supplies upper bound 4, and the new edge improves that to 1. The potentials p(s)=p(a)=p(b)=0, p(t)=1 satisfy every new edge inequality, proving D=1. Only the comparison affected by the new edge had to be replaced.