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

#*****************************************************************************80
#
## I4MAT_SHORTEST_PATH computes the shortest distance between all pairs of points.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    28 January 2016
#
#  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, integer 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.
#
  i4_huge = 2147483647

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

  return m

def i4mat_shortest_path_test ( ):

#*****************************************************************************80
#
## I4MAT_SHORTEST_PATH_TEST tests I4MAT_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 i4mat_print import i4mat_print

  i4_huge = 2147483647

  n = 6

  a = np.array ( [ \
    [  0,  2,  5, -1, -1, -1 ], \
    [ -1,  0,  7,  1, -1,  8 ], \
    [ -1, -1,  0,  4, -1, -1 ], \
    [ -1, -1, -1,  0,  3, -1 ], \
    [ -1, -1,  2, -1,  0,  3 ], \
    [ -1,  5, -1,  2,  4,  0 ] ] )

  print ( '' )
  print ( 'I4MAT_SHORTEST_PATH_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  I4MAT_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".' )

  i4mat_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 ):
        a[i,j] = i4_huge

  a = i4mat_shortest_path ( n, a )

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

  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.' )

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

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