Запуск алгоритма Дейкстры параллельно с использованием Pthreads в C

Question

Привет, я пытаюсь запустить последовательную версию алгоритма Дейкстры параллельно, используя Pthreads.Я успешно сделал это, используя OMP, и теперь я пытаюсь использовать Pthreads.У меня есть следующий код, который я написал // THIS LINE, где я считаю, что я сталкиваюсь с проблемами.

/* Create a stuct to hold data for each thread */
struct ThreadData {
    long start, stop;
    graph G;
};

/* This function gets called from the main */
void testScheduler(int nThreads, graph* G)
{
    resetGraph(G); // Make a fresh graph

    struct ThreadData data[nThreads]; // Create stucts to hold each thread information
    pthread_t threads [nThreads]; // Create threads
    int tasksPerThread = ((G->N)+nThreads-1)/nThreads; // Divide up tasks

    /* Do the loop in NUMTHREADS pieces */
    for (int i=0; i<nThreads; i++) {
        data[i].start=i*tasksPerThread;
        data[i].stop=(i+1)*tasksPerThread;
        data[i].G = *G;
    }
    /* The last thread must not go past the size of the graph */
    data[nThreads-1].stop = (G->N);


    /* Launch Threads */
    for (int i=0; i<nThreads; i++) {
        pthread_create(&threads[i], NULL, dijkstra, &data[i]);
    }
    /* Wait for Threads to Finish */
    for (int i=0; i<nThreads; i++) {
        pthread_join(threads[i], NULL);
    }


}

void dijkstra(struct ThreadData* td)
{
    long i,j;
    struct ThreadData* data=(struct ThreadData*) td; // This threads data
    long start = data->start; // Starting Point
    long stop = data->stop; // Ending Point
    graph* G = &data->G; // The graph
    long aN; //actualNode

    G->D[start] = 0; // THIS LINE 
    aN = start;     // THIS LINE 


    for(i = start; i < stop; i++)
    {
        G->visited[aN] = VISITED;

        //Find all nodes connected to aN
        for(j=start;j<stop;j++){
            if( (G->node[aN][j] != NO_CONN) ){
                if( (G->D[aN] + G->node[aN][j]) < G->D[j] ){
                    G->D[j] = (G->D[aN] + G->node[aN][j]);
                }
            }
        }

        aN = getNextNode(G);
    }

}

В настоящее время я понимаю, что я делаю новую версию Graph G для каждого потока, я сделал это, поэтому мне не нужно использовать блокировки мьютекса.Однако это создает проблему, потому что я не могу получить доступ к текущей переменной aN или G->D до.

Вопросы:

Если я использую глобальный Graph G (с блокировками мьютекса), это означает, что каждый поток должен работать в правильном порядке, чтобы я мог получить переменные из последнего потока иПродолжить?Если да, то есть ли смысл в параллельной работе, если я просто жду завершения каждого предыдущего потока?

Если я использую блокировки мьютекса, нужно ли мне блокироваться при чтении из переменной или только при записи?

Есть ли способ сделать это похожим на текущий способ, который я сделал?

Я плохо знаком с pthreads, извините, если задал какие-то глупые вопросы.