    program mst
      include 'mpif.h'
      integer ndims,xmax,ymax,nnodes
      logical reorder
      parameter(ndims=2,reorder=.true.)
      integer comm,comm_cart,newcomm,dims(ndims),ierr
      integer own_position(ndims)
      logical periods(ndims),remain_dims(ndims)
      integer status(MPI_STATUS_SIZE),coords(ndims),root,rank,size

    integer niters,vdim
    parameter(niters = 10)
    parameter(vdim = 500)
    double precision time_begin,time_end
    integer,allocatable,dimension(:,:)          :: A,Dk,Dk_1
    double precision,allocatable,dimension(:,:) :: temp
    integer,allocatable,dimension(:)            :: UP,LEFT 
    integer shape(2)

    data dims /ndims * 0/
    comm = MPI_COMM_WORLD
    
    call MPI_init(ierr)
    call MPI_COMM_RANK(comm,myid,ierr)
    call MPI_COMM_SIZE(comm,nnodes,ierr)
    call MPI_DIMS_CREATE(nnodes,ndims,dims,ierr)
    periods(1) = .TRUE.
    periods(2) = .TRUE.
    call MPI_CART_CREATE(comm,ndims,dims,periods,reorder,comm_cart,ierr)
    call MPI_CART_GET(comm_cart,ndims,dims,periods,own_position,ierr)
  
    ipos = own_position(1)
    jpos = own_position(2)
    nx  = sqrt(real(nnodes))
    ny  = nx
    xmax = vdim/nx
    ymax = vdim/ny
    allocate(A(vdim,vdim))
    allocate(Dk(xmax,ymax))
    allocate(Dk_1(xmax,ymax))
    allocate(UP(ymax))
    allocate(LEFT(xmax))
    allocate(temp(vdim,vdim))

    shape(1) = vdim 
    shape(2) = vdim
!initialize adjacency matrix elments
    call random_number(temp)
    A  = int(temp*10000.0)
    do i=1,n 
       A(i,i) = 0
    enddo  
   
   !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 )
    Dk = A(jpos*xmax+1:(jpos+1)*xmax,ipos*ymax+1:(ipos+1)*ymax)  
 
!Start Floyd All-to-All shortest path algorithm

    time_begin =  MPI_Wtime()
    do k=1,vdim
      Dk_1 = Dk
      kproc = (k-1)/xmax
      kline = mod(k-1,xmax) + 1

      UP    = Dk_1(kline,:)
      remain_dims(1) = .false.
      remain_dims(2) = .true.
      call MPI_CART_SUB(comm_cart,remain_dims,newcomm,ierr)
      call MPI_CART_RANK(newcomm,kproc,root,ierr) 
      call MPI_BCAST(UP,ymax,MPI_INTEGER,root,newcomm,ierr)

      LEFT = Dk_1(:,kline)
      remain_dims(1) = .true.
      remain_dims(2) = .false.
      call MPI_CART_SUB(comm_cart,remain_dims,newcomm,ierr)
      call MPI_CART_RANK(newcomm,kproc,root,ierr)
      call MPI_BCAST(LEFT,xmax,MPI_INTEGER,root,newcomm,ierr)
      
    
      do i=1,xmax
       do j=1,ymax
          Dk(i,j) = min(LEFT(i) + UP(j),Dk_1(i,j))
       enddo
      enddo
            
    enddo

    time_end =  MPI_Wtime()
    print *,'Elapsed time for ',niters,'iterations  '
    print *,'for Floyd Algorithm is'
    print *,time_end-time_begin

    deallocate(A)
    deallocate(Dk)
    deallocate(Dk_1)
    deallocate(UP)
    deallocate(LEFT)
    deallocate(temp)


  
    end
 
 
  

