Distances as a Certificate - Greedy, with a Certificate: Spanning Trees & Shortest Paths

Shortest-path distances are not just answers; they certify themselves. Every edge must satisfy the distance feasibility inequality, and tight edges reconstruct the shortest-path tree.

highlighted = computed this step

Feasibility inequality

Every edge passes the check d(v) minus d(u) is at most the edge weight. Motivation: a shortest-path answer should prove that no single edge can improve the labels.

d(v)-d(u)\leq w(u,v)

Tight edges

There are 5 tight edges, matching the shortest-path tree. Why: equality identifies the predecessor edges that carry the certified paths.

\text{tight edges}=5

Slack edges

There are 4 slack edges; for C-D the label difference is 2 and its weight is 3. Interpretation: a slack edge is compatible with the labels but is not needed to carry a certified shortest path from A.

C-D:\ 2\leq3

Other slack checks

The other slack checks are 3 at most 6, 3 at most 7, and 5 at most 9. Why: every unused edge is still checked against the final labels, so the certificate covers the whole graph.

A-C,D-E,E-F\text{ are feasible slack checks}

Diagram note

Certificate note: the table is the shortest-path dual certificate for this instance, echoing the certificate idea from earlier duality lessons. Pixel positions are rounded for layout; every number shown is exact.

\text{edge feasibility certifies the labels}