MPI之弗洛伊德最短路径算法

弗洛伊德算法在此不在赘述。
查找资料时发现百度上竟然没有基于MPI的全源最短路径的介绍。
一、直接上代码。

#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* for debugging */
#include <mpi.h>

const int INFINITY = 1000000;

void Read_matrix(int local_mat[], int n, int my_rank, int p, 
      MPI_Comm comm);
void Print_matrix(int local_mat[], int n, int my_rank, int p, 
      MPI_Comm comm);
void Floyd(int local_mat[], int n, int my_rank, int p, MPI_Comm comm);
int Owner(int k, int p, int n);
void Copy_row(int local_mat[], int n, int p, int row_k[], int k);
//void Print_row(int local_mat[], int n, int my_rank, int i);

int main(int argc, char* argv[]) {
   int  n;
   int* local_mat;
   MPI_Comm comm;
   int p, my_rank;

   MPI_Init(&argc, &argv);
   comm = MPI_COMM_WORLD;
   MPI_Comm_size(comm, &p);
   MPI_Comm_rank(comm, &my_rank);

   if (my_rank == 0) {
      printf("How many vertices?\n");
      scanf("%d", &n);
   }
   MPI_Bcast(&n, 1, MPI_INT, 0, comm);
   local_mat = malloc(n*n/p*sizeof(int));

   if (my_rank == 0) printf("Enter the local_matrix\n");
   Read_matrix(local_mat, n, my_rank, p, comm);
   if (my_rank == 0) printf("We got\n");
   Print_matrix(local_mat, n, my_rank, p, comm);
   if (my_rank == 0) printf("\n");

   Floyd(local_mat, n, my_rank, p, comm);

   if (my_rank == 0) printf("The solution is:\n");
   Print_matrix(local_mat, n, my_rank, p, comm);

   free(local_mat);
   MPI_Finalize();

   return 0;
}  /* main */
void Read_matrix(int local_mat[], int n, int my_rank, int p, 
      MPI_Comm comm) { 
   int i, j;
   int* temp_mat = NULL;

   if (my_rank == 0) {
      temp_mat = malloc(n*n*sizeof(int));
      for (i = 0; i < n; i++)
         for (j = 0; j < n; j++)
            scanf("%d", &temp_mat[i*n+j]);
      MPI_Scatter(temp_mat, n*n/p, MPI_INT, 
                  local_mat, n*n/p, MPI_INT, 0, comm);
      free(temp_mat);
   } else {
      MPI_Scatter(temp_mat, n*n/p, MPI_INT, 
                  local_mat, n*n/p, MPI_INT, 0, comm);
   }

}  /* Read_matrix */
void Print_matrix(int local_mat[], int n, int my_rank, int p, 
      MPI_Comm comm) {
   int i, j;
   int* temp_mat = NULL;

   if (my_rank == 0) {
      temp_mat = malloc(n*n*sizeof(int));
      MPI_Gather(local_mat, n*n/p, MPI_INT, 
                 temp_mat, n*n/p, MPI_INT, 0, comm);
      for (i = 0; i < n; i++) {
         for (j = 0; j < n; j++)
            if (temp_mat[i*n+j] == INFINITY)
               printf("i ");
            else
               printf("%d ", temp_mat[i*n+j]);
         printf("\n");
      }
      free(temp_mat);
   } else {
      MPI_Gather(local_mat, n*n/p, MPI_INT, 
                 temp_mat, n*n/p, MPI_INT, 0, comm);
   }
}  /* Print_matrix */
void Floyd(int local_mat[], int n, int my_rank, int p, MPI_Comm comm) {
   int global_k, local_i, global_j, temp;
   int root;
   int* row_k = malloc(n*sizeof(int));

   for (global_k = 0; global_k < n; global_k++) {
      root = Owner(global_k, p, n);
      if (my_rank == root)
         Copy_row(local_mat, n, p, row_k, global_k);
      MPI_Bcast(row_k, n, MPI_INT, root, comm);
      for (local_i = 0; local_i < n/p; local_i++)
         for (global_j = 0; global_j < n; global_j++) {
               temp = local_mat[local_i*n + global_k] + row_k[global_j];
               if (temp < local_mat[local_i*n+global_j])
                  local_mat[local_i*n + global_j] = temp;
         }
   }
   free(row_k);
}  /* Floyd */
int Owner(int k, int p, int n) {
   return k/(n/p);
}  /* Owner */
void Copy_row(int local_mat[], int n, int p, int row_k[], int k) {
   int j;
   int local_k = k % (n/p);

   for (j = 0; j < n; j++)
      row_k[j] = local_mat[local_k*n + j];
}  /* Copy_row */

二、代码实现流程：
（1）程序依据分块的思想实现，每一个进程分得一个邻接矩阵块；
（2）每一个节点都会作为一次支点，支点所在的行会被发送到每一个进程；
（3）各进程通过判断local_mat的距离” > “local_mat[i][k]+local_mat[k][j]”更新邻接矩阵，k是支点；
（4）0号进程收集更新后的邻接矩阵，即获得各节点间的最短路径；

三、核心代码：
（1） if (my_rank == 0) {
printf(“How many vertices?\n”);
scanf(“%d”, &n);
}
程序开始输入节点数。

（2）void Read_matrix(int local_mat[], int n, int my_rank, int p,
MPI_Comm comm) {
int i, j;
int* temp_mat = NULL;

if (my_rank == 0) {
temp_mat = malloc(n*n*sizeof(int));
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf(“%d”, &temp_mat[i*n+j]);
MPI_Scatter(temp_mat, n*n/p, MPI_INT,
local_mat, n*n/p, MPI_INT, 0, comm); //分块
free(temp_mat);
} else {
MPI_Scatter(temp_mat, n*n/p, MPI_INT,
local_mat, n*n/p, MPI_INT, 0, comm);
}

}
如果是0号进程，键入邻接矩阵，不可达则键入较大的数1000000，并向每一个进程分配邻接矩阵块。
（3）void Floyd(int local_mat[], int n, int my_rank, int p, MPI_Comm comm) {
int global_k, local_i, global_j, temp;
int root;
int* row_k = malloc(n*sizeof(int));

for (global_k = 0; global_k < n; global_k++) {
root = Owner(global_k, p, n);
if (my_rank == root)
Copy_row(local_mat, n, p, row_k, global_k);
MPI_Bcast(row_k, n, MPI_INT, root, comm);
for (local_i = 0; local_i < n/p; local_i++)
for (global_j = 0; global_j < n; global_j++) {
temp = local_mat[local_i*n + global_k] + row_k[global_j];
if (temp < local_mat[local_i*n+global_j])
local_mat[local_i*n + global_j] = temp;
}
}
free(row_k);
} /* Flo

global_k 是支点所在的行号，支点所在的进程会把支点所在的行发送给每个进程；每个进程通过比较 temp = local_mat[local_i*n + global_k] + row_k[global_j];
if (temp < local_mat[local_i*n+global_j])
更新各进程的邻接矩阵。

四、实验截图：