使用Dijkstra算法，MPI并行编程解决全源最短路径问题（All-Pairs Shortest Paths Problem)

Publish Date: 2019-10-24

该项目的目标是设计并行算法，并使用Dijkstra算法来解决全源最短路径问题（All-Pairs Shortest Paths Problem) 。

全源最短路径问题：确定给定图中每对顶点之间的最短图形距离。
在全源最短路径问题中，每个顶点到所有顶点的最短距离可以分别计算。因此，MPI框架可用于并行计算最短距离，每个进程负责一部分顶点计算。根据顶点数量和平行比例平均分配所有顶点。在每个进程中，根据当前进程号和进程总数确定每个进程的计算范围。

首先，程序在根进程中读取图形的输入数据，并通过MPI_Bcast函数将图形的顶点数和权重矩阵分配给每个进程。为了方便处理，将图的数据读入并存储在一维数组中。接下来，在每个过程中，使用djkstra算法计算从每个顶点到范围内所有顶点的最短距离。计算完成后，通过MPI_Gatherv函数将每个进程的计算结果收集到根进程中，最后将结果保存到根进程中的文件中。

部分代码

djkstra algorithm 的实现

/**
 * Using djkstra algorithm to calculate the shortest distance between vertices
 *
 * @param graph Graph struct
 * @param start start number of the vertex that calculates the shortest distance
 * @param end end number of the vertex that calculates the shortest distance
 * @return
 */
int *djstra(Graph *graph, int start, int end) {
    int n = graph->vertices_number;
    int *local_result = (int *) malloc(sizeof(int) * (end - start + 1) * n);
    memcpy(local_result, graph->adjacency_matrix + start * n, (end - start + 1) * n * sizeof(int));
    int *mark = (int *) malloc(sizeof(int) * n);
    int vertex_no = start;
    for (; vertex_no <= end; vertex_no++) {
        memset(mark, 0, sizeof(int) * n);
        int i = 0;
        while (i++ < n) {
            int offset = (vertex_no - start) * n;
            int vertex = get_min(local_result + offset, mark, n);
            mark[vertex] = 1;
            int j = 0;
            for (; j < n; j++) {
                if (mark[j] == 1) {
                    continue;
                }
                // updating distance
                if (local_result[offset + vertex] + graph->adjacency_matrix[vertex * n + j] <local_result[offset + j]) {
                    local_result[offset + j] = local_result[offset + vertex] + graph->adjacency_matrix[vertex * n + j];
                }
            }
        }
    }
    return local_result;
}