How to parallelize A* algorithm using Open MP?

I am having trouble parallelizing A* algotithm. I have tried parallelizing individual for loops but that didn't improve anything. In fact serial implementation is still faster than this one. Can you help me improve this or give me some ideas?

while(openSet.size() > 0){
    PAIR current = {};
    int maxVal = INT32_MAX;

    int i;
    #pragma omp parallel for num_threads(tc) ordered schedule(dynamic, 1) private(i) shared(openSet, maxVal, current, fScores)
    for(i = 0;i < openSet.size();i++){
        if(fScores[openSet[i].x * dim + openSet[i].y] < maxVal){
            #pragma omp ordered
            maxVal = fScores[openSet[i].x * dim + openSet[i].y];
            current = openSet[i];
        }
    }

    if(current.x == xEnd && current.y == yEnd){
        elapsed = omp_get_wtime() - start;
        //printMat(gScores, dim);
        printPath("res.txt", mat, cameFrom, current, dim, tc);
        break;
    }

    int rm = check_remove(openSet, current, tc);
    openSet.erase(openSet.begin() + rm);

    vector<PAIR> neighbours;

    if(current.x - 1 >= 0 && mat[(current.x - 1) * dim + current.y] != '1'){
        neighbours.push_back(PAIR(current.x - 1, current.y));
    }
    if (current.y - 1 >= 0 && mat[current.x * dim + (current.y - 1)] != '1'){
        neighbours.push_back(PAIR(current.x, current.y - 1));
    }
    if (current.x + 1 < dim && mat[(current.x + 1) * dim + current.y] != '1'){
        neighbours.push_back(PAIR(current.x + 1, current.y));
    }
    if (current.y + 1 < dim && mat[current.x * dim + (current.y + 1)] != '1'){
        neighbours.push_back(PAIR(current.x, current.y + 1));
    }
    
    int tentative_gScore;
    #pragma omp parallel for num_threads(tc) ordered schedule(dynamic, 1) private(i) shared(neighbours, openSet, gScores, fScores, tentative_gScore)
    for(i = 0;i < neighbours.size();i++){
        tentative_gScore = gScores[current.x * dim + current.y] + 1;

        if(tentative_gScore < gScores[neighbours[i].x * dim + neighbours[i].y]){
            #pragma omp ordered
            cameFrom[neighbours[i].x * dim + neighbours[i].y] = current;
            gScores[neighbours[i].x * dim + neighbours[i].y] = tentative_gScore;
            fScores[neighbours[i].x * dim + neighbours[i].y] = tentative_gScore + hScore(); //(p.x, p.y, xEnd, yEnd)
            if(contains(openSet, neighbours[i]) == false){
                openSet.push_back(neighbours[i]);
            }
        }
    }
}