Shortest Paths and MST Workshop
P9. Algorithm selection
Choose and justify methods for unit hops, signed DAG distances, general nonnegative distances, signed graphs with a reachable negative cycle, and all-pairs distances on a small dense graph. Define unreachable versus unbounded target status.
P10. Dijkstra and stale entries
Trace 0→1:5,0→2:1,2→1:1,1→3:2. Return distances and parent edge IDs. Show the stale heap record and explain why first discovery is insufficient. Derive the lazy-heap bound in V and E, allowing parallel edges.
P11. Relaxation semantics
Trace one snapshot round and one in-place pass over 0→1:1,1→2:1. Then classify every source-0 target for 0→1:2,1→2:-3,2→1:1,2→3:4,0→4:7,5→5:-1. Prove why affected status propagates to descendants, not every reachable vertex.
P12. Matrix DP
Initialize and trace Floyd–Warshall for 0→1:4,0→1:7,1→2:-2,0→2:9. Explain the outer k loop and parallel-edge minimum. Add a negative self-loop on an isolated fourth vertex and classify which pairs become unbounded.
P13. Tied cut and cycle rules
List all MSTs of the all-weight-1 triangle. State the cut/cycle rules with correct some/every qualifiers. Prove the respecting-cut exchange step for a partially chosen forest. Explain why a tie need not produce a contradiction.
P14. Disconnected Kruskal
For four vertices and edges (0,1,2),(1,2,-1),(0,2,4),(1,1,-100), return
minimum-forest weight and original edge IDs. Explain the loop exclusion and V-c
edge count. Design a tiny subset oracle that checks coverage as well as weight.
P15. Prim versus Dijkstra
On 0–1:2,1–2:2,0–2:3, compare an MST to a shortest-path tree rooted at 0. State each key's meaning and the proof that supports it. Extend Prim to disconnected input and explain lazy versus indexed heap storage.
P16. Changed MST objectives
Enumerate trees of a triangle with edge weights 1,2,2. Identify minimum sum, minimum bottleneck, a different optimum and the strictly second-best cost. Explain why dropping zero-cost maximum-edge exchanges can miss the strict answer.
Use Practice Solutions after preserving your independent attempt. Equivalent valid witnesses are accepted.