function [ path_dist, dad, path ] = graph_dist_one ( dist, inode, nnode )

%*****************************************************************************80
%
%% graph_dist_one() computes the distance from one node to all others in a graph.
%
%  Discussion:
%
%    This routine can handle both ordinary graphs and directed graphs.
%
%    In an ordinary graph, a connection between two nodes is always guaranteed
%    to be "symmetric".  That is, if node I is connected to node J by
%    an edge of length D, then node J is connected to node I, and the
%    distance is again D.
%
%    In a directed graph, if node I is connect to node J by an edge of
%    length D, then nothing is known about a possible connection from
%    node J back to node I.  In particular, it is possible that:
%
%    * there is no direct edge from node J to node I;
%    * the edge from node J to node I exists, but is a different "length"
%      than the edge from node I to node J.
%
%    The program computes:
%
%    * PATH_DIST, an array of distances from node INODE to all other nodes;
%
%    * DAD, an array which can be used to determine the path from
%      node INODE to any particular node.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    05 November 2024
%
%  Reference:
%
%    Alan Gibbons,
%    Algorithmic Graph Theory,
%    Cambridge University Press, 1985,
%    ISBN 0-521-28881-9.
%
%  Input:
%
%    real DIST(NNODE,NNODE).  DIST contains the weighted
%    adjacency information defining the graph, or directed graph.
%    The diagonal entries of DIST, that is, DIST(I,I), should be set to 0.
%    The value of the typical off diagonal element DIST(I,J) should
%    represent the length, or weight, of the edge from node I to
%    node J.  If the graph is undirected, then DIST(I,J) should always
%    equal DIST(J,I).  For a directed graph, these quantities may differ.
%    If there is no edge from node I to node J, then it would be natural
%    to set DIST(I,J) to Inf. 
%    All the entries in DIST should be non-negative.  The algorithm will
%    NOT work correctly if negative edge lengths are input.
%    Off-diagonal elements DIST(I,J) may be set to zero.  This simply
%    means that two nodes are "very close", like St Paul and Minneapolis.
%
%    integer INODE, the base node, from which distances to
%    the other nodes are to be calculated.
%
%    integer NNODE, the number of nodes.
%
%  Output:
%
%    real PATH_DIST(NNODE).  On output, for every value
%    of I from 1 to NNODE, PATH_DIST(I) contains the distance from node INODE
%    to node I in the graph.  Of course, PATH_DIST(INODE) is zero.  Moreover,
%    if PATH_DIST(I) = DINFIN, then this is the program's way of reporting that
%    there is NO path from node INODE to node I.
%
%    integer DAD(NNODE), information defining the shortest
%    path from node INODE to any node I, which presumably will be of
%    total distance PATH_DIST(I).
%    The path from node I to node INODE, is recorded "in reverse"
%    in DAD.  The last node is INODE, of course.  The previous node
%    is DAD(INODE).  The next node is DAD(DAD(INODE)) and
%    so on, until INODE itself is reached.
%    If the distance from node I to node INODE is Inf, then
%    DAD will still record a path; it's just probably of no interest.
%
%    integer PATH(NNODE).  The value of PATH(I) records
%    the step on which the distance from INODE to node I was
%    determined.  There will be NNODE steps, and on each step
%    just one such distance is computed.
%

%
%  Initialize the data.
%
  dad = inode * ones ( nnode, 1 );
  path = zeros ( nnode, 1 );
  path_dist = dist(inode,1:nnode);
%
%  On step 1, we connect node INODE itself.
%
  dad(inode) = inode;
  path(inode) = 1;
%
%  On steps ISTEP = 2 through NNODE, we try to add just one more node.
%
%  Of all the nodes which are not yet connected to INODE (because PATH
%  is 0 for this node), choose the one whose distance is least.
%
  for istep = 2 : nnode

    dmin = Inf;
    imin = 0;

    for j = 1 : nnode

      if ( path(j) == 0 )
        if ( path_dist(j) <= dmin )
          dmin = path_dist(j);
          imin = j;
        end
      end

    end
%
%  If we found no new node to add, then any remaining nodes cannot
%  be connected.
%
    if ( dmin == Inf )
      return
    end
%
%  Now add the closest node, labeled IMIN, to the list.
%
    path(imin) = istep;
%
%  Update the distances of the remaining unconnected nodes.
%
    for j = 1 : nnode

      if ( path(j) == 0 )

        dtemp = path_dist(imin) + dist(imin,j);

        if ( dtemp < path_dist(j) )
          path_dist(j) = dtemp;
          dad(j) = imin;
        end

      end

    end

  end

  return
end
