PROGRAM h03adfe

!      H03ADF Example Program Text

!      Mark 23 Release. NAG Copyright 2011.

!      .. Use Statements ..
       USE nag_library, ONLY : f11zaf, h03adf, nag_wp
!      .. Implicit None Statement ..
       IMPLICIT NONE
!      .. Parameters ..
       INTEGER, PARAMETER              :: nin = 5, nout = 6
       CHARACTER (1), PARAMETER        :: dup = 'F', zero = 'R'
!      .. Local Scalars ..
       REAL (KIND=nag_wp)              :: splen
       INTEGER                         :: ifail, j, lenc, n, ne, nnz, ns
       LOGICAL                         :: direct
!      .. Local Arrays ..
       REAL (KIND=nag_wp), ALLOCATABLE :: d(:), work(:)
       INTEGER, ALLOCATABLE            :: icol(:), irow(:), iwork(:), path(:)
!      .. Executable Statements ..
       WRITE (nout,*) 'H03ADF Example Program Results'

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

       READ (nin,*) n, ns, ne, nnz, direct
       ALLOCATE (d(nnz),work(2*n),icol(nnz),irow(nnz),iwork(3*n+1),path(n))

       READ (nin,*) (d(j),irow(j),icol(j),j=1,nnz)

!      Reorder the elements of D into the form required by H03ADF.

       ifail = 0
       CALL f11zaf(n,nnz,d,irow,icol,dup,zero,iwork,iwork(n+2),ifail)

!      Find the shortest path between vertices NS and NE.

       ifail = 0
       CALL h03adf(n,ns,ne,direct,nnz,d,irow,icol,splen,path,iwork,work,ifail)

!      Print details of shortest path.

       lenc = n

LOOP:  DO j = 0, n - 1

          IF (path(j+1)==0) THEN
             lenc = j
             EXIT LOOP
          END IF

       END DO LOOP

       WRITE (nout,99999) 'Shortest path = ', (path(j),j=1,lenc)
       WRITE (nout,99998) 'Length of shortest path = ', splen

99999  FORMAT (/1X,A,10(I2:'  to '))
99998  FORMAT (/1X,A,G16.6)
    END PROGRAM h03adfe