Two Greedy Algorithms - Greedy, with a Certificate: Spanning Trees & Shortest Paths

The capstone compares two correct greedy algorithms on the same graph. The MST is certified by cuts, while the shortest-path tree is certified by distance feasibility, and the resulting trees are not the same.

highlighted = computed this step

MST certificate

The MST total is 19. Motivation: Kruskal, Prim, and the cut-property table give independent checks of the same tree edge set.

w(T_{\text{MST}})=19

Shortest-path certificate

The distance from A to F is 13. Why: Dijkstra labels and edge feasibility certify paths from the chosen start node, not a low total tree weight.

d(F)=13

Different trees

The MST includes C-D with weight 3, while the shortest-path tree includes B-D with weight 4. Interpretation: total tree weight and distance from A are different objectives, so correct certificates can point to different edges.

\text{MST uses }C-D=3\quad \text{SP tree uses }B-D=4

Contrast table

The contrast table gives absent listed edges value 0, so C-D and B-D can be compared directly. Why: the two certificates prove different outputs on the same graph.

\text{absent listed edge}= 0

Recomputed comparison

If the B-D edge weight is changed to 10, the exact shortest-path recompute uses C-D with weight 3 and gives distance to F as 14. Why: the same certificate machinery responds to changed weights without changing the flagship graph.

\text{comparison: }d(F)=14,\ C-D=3

Diagram note

Certificate note: These certificates are exact for this pinned nonnegative weighted graph; general greedy claims and negative-weight shortest paths are outside this lesson. Pixel positions are rounded for layout; every number shown is exact.

\text{different greedy certificates, different objectives}