subroutine tsp_nearest ( n, x, order_best, cost_best )

!*****************************************************************************80
!
!! tsp_nearest() seeks an optimal round trip by the nearest neighbor method.
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    15 July 2026
!
!  Author:
!
!    John Burkardt
!
!  Input:
!
!    integer n: the number of cities.
!
!    real x(n,*): the coordinates of the cities.
!
!  Output:
!
!    integer order_best(n): the order in which the N cities should be visited.
!
!    real cost_best: the length of the optimal round trip.
!
  implicit none

  integer, parameter :: rk8 = kind ( 1.0D+00 )

  integer n

  real ( kind = rk8 ) cost
  real ( kind = rk8 ) cost_best
  integer i
  integer order(n)
  integer order_best(n)
  integer start
  real ( kind = rk8 ) x(n,2)
!
!  Initialize:
!    the best cost so far is Infinity
!    the best tour so far is 1, 2, ..., n.
!
  cost_best = huge ( 1.0D+00 )
  do i = 1, n
    order_best(i) = i
  end do
!
!  Try starting at city START and moving to the nearest neighbor.
!
  do start = 1, n

    call tsp_tour_nearest ( n, x, start, order )
    call tsp_tour_cost ( n, x, order, cost )

    if ( cost < cost_best ) then
      order_best(1:n) = order(1:n)
      cost_best = cost
      write ( *, '(a,i2,a,g14.6)' ) &
        '  Route starting at city ', start, ' has cost ', cost_best
    end if
 
  end do

  return
end
subroutine tsp_tour_cost ( n, x, order, cost )

!*****************************************************************************80
!
!! tsp_tour_cost() evaluates the cost of a round trip.
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    19 June 2026
!
!  Author:
!
!    John Burkardt
!
!  Input:
!
!    integer n: the number of cities.
!
!    real x(n,2): the city locations.
!
!    integer order(n): a permutation of 1:N, the route.
!
!  Output:
!
!    real cost: the cost of the route.
!
  implicit none

  integer, parameter :: rk8 = kind ( 1.0D+00 )

  integer n

  real ( kind = rk8 ) cost
  integer from
  integer order(n)
  integer to
  real ( kind = rk8 ) x(n,2)

  cost = 0.0D+00
  from = n
  do to = 1, n
    cost = cost + sqrt ( ( x(order(from),1) - x(order(to),1) )**2 &
                       + ( x(order(from),2) - x(order(to),2) )**2 )
    from = to
  end do

  return
end
subroutine tsp_tour_nearest ( n, x, start, order )

!*****************************************************************************80
!
!! tsp_tour_nearest() finds a nearest neighbor route for a given start.
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    15 July 2026
!
!  Author:
!
!    John Burkardt
!
!  Input:
!
!    integer n: the number of cities.
!
!    real x(n,2): the city to city distance table.
!
!    integer start: the starting city.
!
!  Output:
!
!    integer order(n): the route that starts at START.
!
  implicit none

  integer, parameter :: rk8 = kind ( 1.0D+00 )

  integer n

  real ( kind = rk8 ) d(n,n)
  real ( kind = rk8 ) dmin
  integer from
  integer i
  integer j
  integer k
  integer order(n)
  integer start
  integer to
  real ( kind = rk8 ) x(n,2)
!
!  Make a copy of the distance table that we can modify.
!
  do i = 1, n
    do j = 1, n
      d(i,j) = sqrt ( ( x(i,1) - x(j,1) )**2 &
                    + ( x(i,2) - x(j,2) )**2 )
    end do
    d(i,i) = huge ( 1.0D+00 )
  end do
!
!  At FROM, find nearest unvisited city TO.
!
  do j = 1, n

    if ( j == 1 ) then
      to = start
    else
      to = 1
      dmin = d(from,to)
      do k = 1, n
        if ( d(from,k) < dmin ) then
          to = k
          dmin = d(from,to)
        end if
      end do
    end if
!
!  Add TO to path, and move there.
!
    order(j) = to
    from = to
!
!  Reset D so we can't revisit city TO.
!
    do i = 1, n
      d(i,to) = huge ( 1.0D+00 )
    end do

  end do

  return
end