#! /usr/bin/env python
#
def r8mat_shortest_path ( n, m ):

#*****************************************************************************80
#
## R8MAT_SHORTEST_PATH computes the shortest distance between all pairs of points.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    01 March 2014
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Robert Floyd,
#    Algorithm 97, Shortest Path,
#    Communications of the ACM,
#    Volume 5, Number 6, June 1962, page 345.
#
#  Parameters:
#
#    Input, integer N, the number of points.
#
#    Input/output, real M(N,N).
#    On input, M(I,J) contains the length of the direct link between 
#    nodes I and J, or Inf if there is no direct link.
#    On output, M(I,J) contains the distance between nodes I and J,
#    that is, the length of the shortest path between them.  If there
#    is no such path, then M(I,J) will remain Inf.
#
  r8_huge = 1.0E+30

  for i in range ( 0, n ):
    for j in range ( 0, n ):
      if ( m[j,i] < r8_huge ):
        for k in range ( 0, n ):
          if ( m[i,k] < r8_huge ):
            s = m[j,i] + m[i,k]
            if ( s < m[j,k] ):
              m[j,k] = s

  return m

def r8mat_shortest_path_test ( ):

#*****************************************************************************80
#
## R8MAT_SHORTEST_PATH_TEST tests R8MAT_SHORTEST_PATH.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    28 January 2016
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform
  from r8mat_print import r8mat_print

  r8_huge = 1.0E+30

  n = 6

  a = np.array ( [ \
    [  0.0,  2.0,  5.0, -1.0, -1.0, -1.0 ], \
    [ -1.0,  0.0,  7.0,  1.0, -1.0,  8.0 ], \
    [ -1.0, -1.0,  0.0,  4.0, -1.0, -1.0 ], \
    [ -1.0, -1.0, -1.0,  0.0,  3.0, -1.0 ], \
    [ -1.0, -1.0,  2.0, -1.0,  0.0,  3.0 ], \
    [ -1.0,  5.0, -1.0,  2.0,  4.0,  0.0 ] ] )
 
  print ( '' )
  print ( 'R8MAT_SHORTEST_PATH_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  R8MAT_SHORTEST_PATH uses Floyd\'s algorithm to find the' )
  print ( '  shortest distance between all pairs of nodes' )
  print ( '  in a directed graph, starting from the initial array' )
  print ( '  of direct node-to-node distances.' )

  print ( '' )
  print ( '  In the initial direct distance array, if' )
  print ( '    A(I,J) = Inf,' )
  print ( '  this indicates there is NO directed link from' )
  print ( '  node I to node J.  In that case, the value of' )
  print ( '  of A(I,J) is essentially "infinity".' )

  r8mat_print ( n, n, a, '  Initial direct-link distances:' )

  for j in range ( 0, n ):
    for i in range ( 0, n ):
      if ( a[i,j] == -1.0 ):
        a[i,j] = r8_huge

  a = r8mat_shortest_path ( n, a )

  for j in range ( 0, n ):
    for i in range ( 0, n ):
      if ( a[i,j] == r8_huge ):
        a[i,j] = -1.0

  print ( '' )
  print ( '  In the final shortest distance array, if' )
  print ( '    A(I,J) = -1,' )
  print ( '  this indicates there is NO directed path from' )
  print ( '  node I to node J.' )

  r8mat_print ( n, n, a, '  Final distance matrix:' )
#
#  Terminate.
#
  print ( '' )
  print ( 'R8MAT_SHORTEST_PATH_TEST' )
  print ( '  Normal end of execution.' )
  return

if ( __name__ == '__main__' ):
  from timestamp import timestamp
  timestamp ( )
  r8mat_shortest_path_test ( )
  timestamp ( )