Subscribe to the weekly news from TrueShelf

0

Minimum-weight spanning path

Let \(G\) be an undirected weighted complete graph. Iteratively select the edge of least weight such that the edges selected so far form a disjoint union of paths. After \(n-1\) steps, the result is a spanning path.

Give an infinite family of counterexamples where this algorithm fails to produce a minimum-weight spanning path.

Related Content