program mst
    integer niters,vdim
    parameter(niters = 10)
    parameter(vdim = 500)
    double precision time_begin,time_end
    integer,dimension(vdim)   :: dis_vec
    integer,dimension(vdim,vdim)        :: A,Dk,Dk_1
    double precision temp(vdim,vdim)
     
    integer shape(2),res(1)
    logical flag(vdim)

    !HPF$ DISTRIBUTE (BLOCK,BLOCK)     :: A,Dk,Dk_1


    shape(1) = vdim 
    shape(2) = vdim
!initialize adjacency matrix elments
    call random_number(temp)
    A  = int(temp*10000.0)
   
   ! A = reshape( (/0,1,3,99,99,2,1,0,5,1,99,99,3,5,0,2,1,99,99,1,2,0,4,&
   !             99,99,99,1,4,0,5,2,99,99,99,5,0/),shape )
   forall(i=1:vdim) A(i,i) = 0  

!Start Floyd All-to-All shortest path algorithm
    print *,elapsed_time()
    n = vdim
    Dk = A    
    do k=1,n
      Dk_1 = Dk
      forall(i=1:n,j=1:n)
         Dk(i,j) = min(Dk_1(i,k) + Dk_1(k,j),Dk_1(i,j))
      endforall
    enddo
    
    print *,'Elapsed time for ',niters,'iterations  '
    print *,'for Floyd Algorithm is'
    print *,elapsed_time()

  
    end
 
    double precision function elapsed_time()
      integer :: clock_count, clock_rate, clock_max
      integer, save :: last_count
      logical, save :: system_clock_not_yet_called = .true.
 
      call system_clock(count=clock_count,&
                       count_rate=clock_rate, &
                       count_max=clock_max)
      if (system_clock_not_yet_called) then
         system_clock_not_yet_called = .false.
         elapsed_time = 0.0
      else if (clock_count > last_count) then
         elapsed_time = real (clock_count-last_count)/real(clock_rate)
      else
         elapsed_time = real (clock_max-last_count+clock_count)&
                  /real(clock_rate)
      end if
      last_count = clock_count
      return
     end function elapsed_time