Skip to main content

Algorithms · Dynamic programming and state design

Prim’s algorithm starts at an arbitrary root and repeatedly adds a minimum-weight edge…

Problem

Algorithms practice problem

Prim’s algorithm starts at an arbitrary root and repeatedly adds a minimum-weight edge with exactly one endpoint in the current tree. State and prove an invariant connecting the current tree to some minimum spanning tree. Use it to prove correctness for graphs with repeated and negative edge weights, and explain formally why the choice of starting root cannot change the minimum possible output weight.

Hint

Hint

** Let AA be the selected edges and SS the reached vertices.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Algorithms sample problem: Try the free sample problem.

More Algorithms practice problems

Back to Algorithms

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.