Try out NAG Library functions

Explore NAG maths and stats routines with interactive demos
Function ID
H03ADF
Name
nagf_mip_shortestpath
Description
Shortest path problem, Dijkstra's algorithm
Keywords
Dijkstra's algorithm, shortest path | shortest path
The example data reflects that shown in the "Example" section of the routine documentation. You can change this here to try alternative inputs. The formatting will need to be kept as it is here, otherwise the program is likely to fail to run correctly.

Please note that incompatible data will however cause the example output to display an error message. These error messages are fully explained in the Routine document
    Program h03adfe

!     H03ADF Example Program Text

!     Mark 26 Release. NAG Copyright 2016.

!     .. 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
The NAG Library
The world’s largest collection of robust, documented, tested and maintained numerical algorithms.
Learn more here or contact us for purchasing information