    program mst
    include 'mpif.h'
    integer niters,vdim
    parameter(niters = 10)
    parameter(vdim = 1000)
    parameter(INFINITI = 99999999)
    double precision time_begin,time_end
    integer,allocatable,dimension(:)   :: dis_vec,dis_vec_copy
    integer,allocatable,dimension(:,:) :: adj_mat,adj_mat_copy,in,out
    double precision ,allocatable,dimension(:,:) ::temp
    integer status(MPI_STATUS_SIZE),root,comm,myid,nnodes
    logical,allocatable,dimension(:)   :: flag 
     
    integer shape(2),res(1)

    comm = MPI_COMM_WORLD
    call MPI_init(ierr)
    call MPI_COMM_RANK(comm,myid,ierr)
    call MPI_COMM_SIZE(comm,nnodes,ierr)
    
    nblok = vdim/nnodes

    allocate(dis_vec(nblok))
    allocate(adj_mat(vdim,nblok))
    allocate(adj_mat_copy(vdim,vdim))
    allocate(dis_vec_copy(nblok))
    allocate(in(2,nblok))
    allocate(out(2,nblok))
    allocate(temp(vdim,vdim))
    allocate(flag(nblok))

    shape(1) = vdim
    shape(2) = vdim
!initialize adjacency matrix elments
   call random_number(temp)
   adj_mat_copy = int(temp*10000.0)
   do i=1,vdim
     adj_mat_copy(i,i) = 0
   enddo
  
  ! adj_mat_copy = 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 )
              
   adj_mat = adj_mat_copy(:,myid*nblok+1:(myid+1)*nblok)

!initialize distance vector array
    
    time_begin =  MPI_Wtime()
    do iter =1,niters
       flag = .TRUE.
       dis_vec = adj_mat(1,:)
       dis_vec_copy =  dis_vec
       if (myid == 0) then
         dis_vec(1) =  INFINITI
         flag(1) = .FALSE.
       endif
    
       do i= 1,vdim-1
         in(1,:) = dis_vec
         in(2,:) = myid
         call MPI_ALLREDUCE(in,out,nblok,MPI_2INTEGER,MPI_MINLOC,&
            comm,ierr)
         res = minloc(out(1,:))
         min_proc = out(2,res(1))
         min_line = min_proc*nblok+res(1)
         if (myid == min_proc ) then
           dis_vec(res(1)) = INFINITI
           flag(res(1)) = .FALSE.
         endif   
         
         do j = 1,nblok
           if ((adj_mat(min_line,j) < dis_vec(j)) .and. flag(j) ) then
             dis_vec(j)  = adj_mat(min_line,j) 
             dis_vec_copy(j) = dis_vec(j) 
           endif
         enddo

       enddo
    enddo
    time_end =  MPI_Wtime()

    print *,'Elapsed time for ',niters,'iterations  '
    print *,'for minimum spanning tree is'
    print *,time_end-time_begin

    deallocate(adj_mat)
    deallocate(temp)
    deallocate(adj_mat_copy)
    deallocate(dis_vec)
    deallocate(dis_vec_copy)
    deallocate(in)
    deallocate(out)
     deallocate(flag) 
     
    call MPI_FINALIZE(ierr)

  
    end
 
 
  
