Prev     Next
Is the Algorithm Correct?

Instructions: This is a non-rigorous argument that demonstrates why the algorithm is correct. It follows a line of reasoning that can be used to rigorously show correctness. Click on "Update" to show, with green lines, a solution obtained by the algorithm on some hypothetical input. We hypothesize that the algorithm is incorrect and a better solution exists. In fact, we draw the hypothetical, absolutely best possible solution in red, as seen by clicking the "Solve" button. Some lines are colored red and green (the best solution and the solution obtained by our algorithm agree on these power lines), some are colored only red (in the best solution but not the algorithm's), and some are colored only green (the algorithm got these but they are not in the best solution). At the upper left of the figure there is a triangle containing a lone red line of cost 89, a lone green line (marked "< 89") and a double colored line. The algorithm always chooses the lowest cost, unconsidered line to add to the partial solution. Since it choose the green line marked "< 89" instead of the red line marked "89", the green line must have cost less than 89 and that is why it is marked "< 89". But this means a solution better than that of the red lines must exist: just replace the 89 line with the "< 89" line - this is shown by clicking on the "Switch" button. But that is impossible since we hypothesized the red solution to be the best possible. Hence it it impossible to have a better solution that the green one which is the one obtained by the algorithm.