Параллелизация OpenMP медленнее, чем последовательная

Question

Я реализовал алгоритм Дейкстры в C. Я пытаюсь сравнить время выполнения с использованием и без использования OpenMP, но по какой-то причине OpenMP всегда медленнее.Я читал кое-что о том, насколько дорогие новые темы, но расширение графика не решает проблему.

Я хотел бы использовать omp здесь

#pragma omp parallel for
for(index=0; index<nodes[n].size; index++){
        int ct = nodes[n].paths[index].connectsTo;
        if(notVisited[ct]){
            int dist = dis[n]+nodes[n].paths[index].weight;
            if(dist<dis[ct]){
                prev[ct] = n;
                dis[ct] = dist;
            }
        }
    }