subroutine floyd ( n, a, b )

!*****************************************************************************80
!
!! floyd() computes the shortest distances between pairs of nodes in a directed graph.
!
!  Discussion:
!
!    We assume we are given the adjacency matrix A of the directed graph.
!
!    We assume that A is an R8MAT, that is, a two-dimensional array of R8's.
!
!    The adjacency matrix is NOT assumed to be symmetric.
!
!    If there is not a direct link from node I to node J, the distance
!    would formally be infinity.  We assume that such distances are assigned 
!    the value HUGE.
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    26 November 2008
!
!  Author:
!
!    John Burkardt
!
!  Input:
!
!    integer N, the order of the matrix.
!
!    real ( kind = rk ) A(N,N), the direct distance from node I to node J.
!
!  Output:
!
!    real ( kind = rk ) B(N,N), the shortest distance from node I to node J.
!
  implicit none

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

  integer n

  real ( kind = rk ) a(n,n)
  real ( kind = rk ) b(n,n)
  integer i
  integer j
  integer k

  b(1:n,1:n) = a(1:n,1:n)

  do k = 1, n
    do j = 1, n
      if ( b(k,j) < huge ( 1.0D+00 ) ) then
        do i = 1, n
          if ( b(i,k) < huge ( 1.0D+00 ) ) then
            b(i,j) = min ( b(i,j), b(i,k) + b(k,j) )
          end if
        end do
      end if
    end do
  end do

  return
end