function [ itree, jtree ] = graph_dist_min_span_tree ( nnode, dist )

%*****************************************************************************80
%
%% graph_dist_min_span_tree() computes a spanning tree of minimal length.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    05 November 2024
%
%  Author:
%
%    Original FORTRAN77 version by Albert Nijenhuis, Herbert Wilf.
%    This version by John Burkardt.
%
%  Reference:
%
%    Albert Nijenhuis, Herbert Wilf,
%    Combinatorial Algorithms,
%    Academic Press, 1978, second edition,
%    ISBN 0-12-519260-6.
%
%  Input:
%
%    integer NNODE, the number of nodes.
%
%    real DIST(NNODE,NNODE).  DIST(I,J) = distance from node I to node J.
%
%  Output:
%
%    integer ITREE(NNODE-1), JTREE(NNODE-1), the pairs of
%    nodes that form the edges of the tree.
%
  for i = 1 : nnode - 1
    itree(i) = i;
  end

  jtree(1:nnode-1) = - nnode;

  for j = 1: nnode - 1
%
%  Choose the node IMIN whose tree edge ( ITREE(IMIN)=IMIN, JTREE(IMIN) )
%  will be set.
%
    dmin = Inf;

    for i = 1 : nnode - 1

      it = jtree(i);

      if ( it < 0 )

        d = dist(-it,i);

        if ( d < dmin )
          dmin = d;
          imin = i;
        end

      end

    end

    jtree(imin) = - jtree(imin);

    for i = 1 : nnode-1

      it = jtree(i);

      if ( it < 0 )
        if ( dist(i,imin) < dist(i,-it) )
          jtree(i) = - imin;
        end
      end

    end

  end

  return
end
