使用openmp实现最短路径算法并行化程序代码

下面是一个使用OpenMP实现最短路径算法并行化的示例代码：

#include <iostream>
#include <vector>
#include <omp.h>

const int INF = INT_MAX;

// 并行化的最短路径算法
void parallelShortestPath(std::vector<std::vector<int>>& graph) {
    int numVertices = graph.size();

    // 初始化距离矩阵
    std::vector<std::vector<int>> dist(numVertices, std::vector<int>(numVertices));
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            dist[i][j] = graph[i][j];
        }
    }

    // 并行计算最短路径
    for (int k = 0; k < numVertices; ++k) {
        #pragma omp parallel for
        for (int i = 0; i < numVertices; ++i) {
            for (int j = 0; j < numVertices; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 打印最短路径矩阵
    std::cout << "Shortest Path Matrix:" << std::endl;
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            if (dist[i][j] == INF) {
                std::cout << "INF" << " ";
            } else {
                std::cout << dist[i][j] << " ";
            }
        }
        std::cout << std::endl;
    }
}

int main() {
    std::vector<std::vector<int>> graph = {
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0}
    };

    parallelShortestPath(graph);

    return 0;
}

这个示例程序使用了OpenMP的 parallel for 指令来并行地计算最短路径。在每一次迭代中，算法会计算距离矩阵中所有顶点对之间的最短路径。由于并行计算，每次迭代的计算会被多个线程同时执行，从而加快了算法的运行速度。

请注意，在使用OpenMP并行化计算时，需要确保并行计算的部分是线程安全的，即不会因为多线程的执行而产生竞争条件。在这个示例程序中，由于每个线程都只修改了 dist 矩阵的局部区域，所以不存在竞争条件。

此外，在编译时需要使用 -fopenmp 选项来开启OpenMP支持，例如：

g++ -fopenmp shortest_path.cpp -o shortest_path

这样编译后的可执行文件就支持OpenMP并行化了