Эффективный способ многопоточной реализации данного алгоритма - это одновременное обновление значений заданной матрицы.

Корректность способа:

A[ i ][ j ]=min(A[ i ][ j ],A[ i ][ k ]+A[ k ][ j ]);

Пусть i=k:

A[ k ][ j ]=min(A[ k ][ j ],A[ k ][ k ]+A[ k ][ j ])

но A[ k ][ k ]=0 значит A[ k ][ j ] не изменится

аналогично доказывается для j=k.

Мы доказали что потоки работающие с разными строками матрицы полностью независимы.

Реализация многопоточного алгоритма.

int **d1,*dco,*dce;

int i,j,k;

#pragma omp parallel private(k,i,j,dce,dco)
  for (k=0;k<size;++k){
   dco=d1[k];
   #pragma omp for
    for (i=0;i<size;++i){
     dce=d1[i];
     for (j=0;j<size;++j)
      if (dce[j]>dce[k]+dco[j])
       dce[j]=dce[k]+dco[j];
    };
  };