function [ inode, jnode ] = graph_dist_min_span_tree3 ( nnode, dist )

%*****************************************************************************80
%
%% graph_dist_min_span_tree3() finds a minimum spanning tree.
%
%  Discussion:
%
%    The input graph is represented by a distance matrix.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    06 November 2024
%
%  Reference:
%
%    Hang Tong Lau,
%    Combinatorial Heuristic Algorithms in FORTRAN,
%    Springer Verlag, 1986.
%
%  Input:
%
%    integer NNODE, the number of nodes.
%
%    real DIST(NNODE,NNODE), an NNODE by NNODE distance
%    matrix.  DIST(I,J) is the distance from node I to node J.  The matrix
%    should be symmetric.  If there is no arc from node I to node J,
%    set DIST(I,J) = HUGE(1.0).
%
%  Output:
%
%    integer INODE(NNODE), JNODE(NNODE); entries 1 through
%    NNODE-1 describe the edges of the spanning tree as pairs of nodes.
%
  work = Inf * ones ( nnode, 1 );
  iwork1 = zeros ( nnode, 1 );
  iwork2 = zeros ( nnode, 1 );
%
%  Find the first non-zero arc.
%
  for ij = 1 : nnode
    flag = 0;
    for kj = 1 : nnode
      if ( dist(ij,kj) < Inf )
        i = ij;
        flag = 1;
        break;
      end
    end
    if ( flag == 1 )
      break;
    end
  end

  work(i) = 0;
  iwork1(i) = 1;
  tree_length = 0.0;
  kk4 = nnode - 1;

  for jj = 1 : kk4

    work = Inf * ones ( nnode, 1 );

    for i = 1 : nnode
%
%  For each forward arc originating at node I calculate
%  the length of the path to node I
%
      if ( iwork1(i) == 1 )
        for j = 1 : nnode
          if ( dist(i,j) < Inf && iwork1(j) == 0 )
            d = tree_length + dist(i,j);
            if ( d < work(j) )
              work(j) = d;
              iwork2(j) = i;
            end
          end
        end
      end

    end
%
%  Find the minimum potential.
%
    d = Inf;
    ient = 0;

    for i = 1 : nnode
      if ( iwork1(i) == 0 && work(i) < d )
        d = work(i);
        ient = i;
        itr = iwork2(i);
      end
    end
%
%  Include the node in the current path.
%
    if ( d < Inf )
      iwork1(ient) = 1;
      tree_length = tree_length + dist(itr,ient);
      inode(jj) = itr;
      jnode(jj) = ient;
    end

  end

  return
end
