PROGRAM nag_short_path_ex01

      ! Example Program Text for nag_short_path
      ! NAG fl90, Release 4. NAG Copyright 2000.

      ! .. Use Statements ..
      USE nag_examples_io, ONLY : nag_std_in, nag_std_out
      USE nag_short_path, ONLY : nag_short_path_find
      ! .. Implicit None Statement ..
      IMPLICIT NONE
      ! .. Intrinsic Functions ..
      INTRINSIC KIND
      ! .. Parameters ..
      INTEGER, PARAMETER :: wp = KIND(1.0D0)
      ! .. Local Scalars ..
      INTEGER :: j, nnz, num_vertex
      REAL (wp) :: short_path_len
      LOGICAL :: undirected
      ! .. Local Arrays ..
      INTEGER, ALLOCATABLE :: col_index(:), row_index(:)
      INTEGER, POINTER :: path(:)
      REAL (wp), ALLOCATABLE :: distance(:)
      ! .. Executable Statements ..
      WRITE (nag_std_out,*) 'Example Program Results for nag_short_path_ex01'

      READ (nag_std_in,*)          ! Skip heading in data file

      ! Read number of non-zeros (nnz)
      READ (nag_std_in,*) nnz

      ALLOCATE (col_index(nnz),row_index(nnz),distance(nnz)) ! Allocate storage

      ! Read in problem data
      READ (nag_std_in,*) num_vertex, undirected
      READ (nag_std_in,*) (distance(j),row_index(j),col_index(j),j=1,nnz)

      ! Find the shortest path between vertices 1 and num_vertex

      CALL nag_short_path_find(num_vertex,distance,row_index,col_index, &
       short_path_len,path,undirected=undirected)

      ! Print details of shortest path

      WRITE (nag_std_out,fmt='(/ 1x, a, 10(i2, :, '' to ''))') &
       'Shortest path = ', path
      WRITE (nag_std_out,fmt='(/ 1x, a, g16.7 )') 'Length of shortest path = ' &
       , short_path_len

      DEALLOCATE (col_index,row_index,distance,path) ! Deallocate storage

    END PROGRAM nag_short_path_ex01