c-----------------------------------------------------------
c Chapter 30: Tree of Minimal Length(p283)
c-----------------------------------------------------------
c   Name of subroutine: MINSPT
c
c   Algorithm:Find spanning tree of minimal length.
c
c-----------------------------------------------------------

c-----The driver program is in minspt_2.f-------------------

c-----Subroutine begins here--------------------------------
      subroutine minspt(n,ndim,dist,tree)
      real dist(n,n)
      integer tree(n)
      nm1=n-1
20    do 21  i=1,nm1
21    tree(i)=-n
      tree(n)=0
25    do 51 l=1,nm1
      dmin=1.e50
40    do 41 i=1,nm1
      it=tree(i)
      if(it.gt.0) go to 41
      d=dist(-it,i)
      if(d.ge.dmin) go to 41
      dmin=d
      imin=i
41    continue
      tree(imin)=-tree(imin)
50    do 51 i=1,nm1
      it=tree(i)
      if(it.gt.0) go to 51
      if(dist(i,imin).lt.dist(i,-it)) tree(i)=-imin
51    continue
      return
      end