From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

In both algorithms, an edge can only ever be picked once, so they will both eventually terminate regardless of negative edge weights. I also suspect that they still generate minimum spanning trees, but don't have a proof of it.

Back to Chapter 8