Proof of Prim's algorithm

From Mathematics

Prim's algorithm yields a minimal spanning tree.

[edit] Proof

Let be the spanning tree on generated by Prim's algorithm, which must be proved to be minimal, and let be spanning tree on , which is known to be minimal.

If , then is minimal.

If , let be the first edge chosen by Prim's algorithm which is not in , chosen on the 'th iteration of Prim's algorithm. Let be the path from to in , and let be an edge in such that one endpoint is in the tree generated at the 'th iteration of Prim's algorithm and the other is not, i.e., one endpoint of is or one endpoint is , but the endpoints are not and .

If the weight of is less than the weight of , then Prim's algorithm would have chosen it on its th iteration, so it is certain that . In particular, when has weight equal to that of , the choice between the two is arbitrary. Whether the weight of is greater than or equal to , can be substituted with while preserving minimal total weight of . This process can be repeated indefinitely, until is equal to , and it is shown that the tree generated by any instance of Prim's algorithm is a minimal spanning tree.

QED