A new correctness proof for prim's algorithm
Bernhard Möller, Peter Höfner · OPUS (Augsburg University) · 2019
We present a new correctness proof for Prim's algorithm.The standard proof establishes the invariant that each iteration constructs a subtree of some minimal spanning tree, and heavily relies on the existence of a spanning tree of the overall graph, as well as an 'edge exchange' property, which includes reasoning about graph cycles.We establish a stronger property showing that the algorithm builds a minimal spanning tree in each step, w.r.t. the vertices already covered.As a consequence, the proof neither uses the existence of a minimal spanning tree of the entire graph, nor the classical exchange property.