We give improved solutions for the problem of generating the
k smallest spanning trees in a graph and in the plane. Our algorithm for general graphs takes time
O(
mlog
(
m, n)+
k
2); for planar graphs this bound can be improved to
O(
n+
k
2). We also show that the
k best spanning trees for a set of points in the plane can be computed in time
O(min(
k
2
n+
nlog
n,
k
2+
knlog(
n/k))). The
k best orthogonal spanning trees in the plane can be found in time
O(
nlog
n+
knloglog(
n/k)+
k
2).