Форум программистов, компьютерный форум, киберфорум
OpenMP
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
0 / 0 / 0
Регистрация: 04.12.2019
Сообщений: 12

Распараллеливание алгоритма Беллмана-Форда

26.10.2022, 14:11. Показов 1605. Ответов 4
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Есть код, который реализует алгоритм Беллмана-Форда. Последовательно работает нормально. Но нужно его распараллелить. Я пробовал, но получается ровно никак. Вроде бы считает на нескольких потоках ,но время расчета не уменьшается, в сравнении с однопоточным расчетом. Помогите, пожалуйста, нормально распараллелить

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <math.h>
#include <ctime>
#include <omp.h>
 
#ifndef _OPENMP
static_assert(false, "openmp support required");
#endif
 
using namespace std;
 
const int INF = INFINITY;
const int Vmax = 10000;
const int Emax = Vmax * (Vmax - 1) / 2;
 
struct edges {
    int u, v, w;
};
 
int i, j, start_peak;
int peak = 0;
int e = 0;
edges edge[Emax];
int d[Vmax];
 
int num_threads;
 
//главная функция
int main()
{
    srand(time(0));
    setlocale(LC_ALL, "Rus");
    int weight;
 
    cout << "Количество вершин > "; cin >> peak;
 
 
    //Заполнение графа
    for (i = 0; i < peak; i++) {
        for (j = 0; j < peak; j++)
        {
            //cout << "Вес " << i + 1 << "->" << j + 1 << " > "; 
            weight = rand() % 100; //cout << w << endl;
            //cin >> w;
            if (weight != 0)
            {
                edge[e].v = i;
                edge[e].u = j;
                edge[e].w = weight;
                e++;
            }
        }
    }
 
    cout << "Стартовая вершина > "; cin >> start_peak;
 
    cout << "Кол-во потоков: "; cin >> num_threads; cout << endl;
 
    for (int i = 0; i < peak; i++) {
        d[i] = INF;
        d[start_peak] = 0;
    }
 
    //num_threads = 3;
 
    int start_t = omp_get_wtime();
    omp_set_dynamic(0);
    omp_set_num_threads(num_threads);
    #pragma omp parallel
    {
    #pragma omp for schedule (static)   
        for (int i = 0; i < peak - 1; i++) {
            for (int j = 0; j < e; j++) {
                if (d[edge[j].v] + edge[j].w < d[edge[j].u]) {
                    d[edge[j].u] = d[edge[j].v] + edge[j].w;
                }
            }
        }
        int end_t = omp_get_wtime();
        cout << endl << "Время расчета: " << 1000 * (end_t - start_t) << " мс"; cout << endl;
 
        //Вывод кратчайших путей
        //cout << "Список кратчайших путей:";
        //for (i = 0; i < n; i++) if (d[i] == inf)
            //cout << endl << start_peak << "->" << i + 1 << "=" << "Not";
        //else cout << endl << start_peak << "->" << i + 1 << "=" << d[i];
    }
 
    system("pause");
    return 0;
}
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
26.10.2022, 14:11
Ответы с готовыми решениями:

Распараллеливание алгоритма интегрирования методом прямоугольников, трапеций и Симпсона с Open MP
Пишу ВКР. Написал небольшую программу, которая должна вычислять интегралы тремя разными способами. Я их засунул в функции. Там 6 функций...

Реализация алгоритма Форда-Беллмана
Всем привет! Бьюсь весь день уже. Нужно реализовать алгоритм Форда-Беллмана, который будет считать кротчайшие пути до других вершин. ...

Реализация алгоритма Форда-Беллмана
Задача: Пользователь задает числа N и M, количество вершин и ребер ориентированного графа. Далее пользователь вводит M строк вида u, v, w,...

4
631 / 526 / 104
Регистрация: 05.08.2022
Сообщений: 2,810
26.10.2022, 14:36
А что вы параллелите? тот цикл, что под #pragma ?
У вас цикл вложен в цикл, но внутри не используется индекс i
Это как и зачем тогда внешний цикл?
0
0 / 0 / 0
Регистрация: 04.12.2019
Сообщений: 12
26.10.2022, 14:50  [ТС]
Честно говоря код не мой и я слабо представляю, как он работает. Как я понял внешний цикл перебирает весь граф n-1 раз. И это же делает вложенный, но уже без этого -1 элемента. А как это параллелить непонятно(
0
631 / 526 / 104
Регистрация: 05.08.2022
Сообщений: 2,810
26.10.2022, 15:01
Лучший ответ Сообщение было отмечено Klukva10 как решение

Решение

Цитата Сообщение от Klukva10 Посмотреть сообщение
я слабо представляю, как он работает
А, ну удачи тогда
0
694 / 304 / 99
Регистрация: 04.07.2014
Сообщений: 851
27.10.2022, 18:19
Цитата Сообщение от Klukva10 Посмотреть сообщение
Честно говоря код не мой и я слабо представляю, как он работает.
В том и дело, что надо разобраться и с кодом и конкретным алгоритмом.

https://ru.wikipedia.org/wiki/... 0%B4%D0%B0

Читаем и смотрим

Первый алгоритм нам не подходит. т.к. при параллельном выполнении кода
Code
1
2
if d[v]>d[u]+w(u,v)
      then d[v] <- d[u]+w(u,v)
мы не знаем когда будут меняться d[v] и d[u], а это приведёт к сбою алгоритма.

Второй алгоритм более интересный
Code
1
2
3
  if A[v,i]>A[u,i-1]+w(u,v)
      then A[v,i] <- A[u,i-1]+w(u,v)
             P[v,i] <- u
Мы не можем параллелить внешний цикл по i, т.к. есть явная зависимость от предыдущего шага.
Напрямую параллелить цикл по ребрам (u,v) тоже не можем, т.к. есть зависимость по v
Но второй цикл можно разбить на два: по v и по u.
т.е.
Code
1
2
3
for i
  for v
    fot u
В этом случае можем независимо считать каждое v, т.е. этот цикл и можем параллелить.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
27.10.2022, 18:19
Помогаю со студенческими работами здесь

Псевдокод алгоритма Беллмана-Форда
У кого есть, скиньте, пожалуйста. Заранее спасибо!

Реализация алгоритма Беллмана-Форда
Написать программу, которая реализовывает алгоритм Беллмана-Форда на C#

Реализация алгоритма Форда-Беллмана
помогите редактировать код так чтобы не делать V-1 итераций, остановить цикл если следующие итерации не уменьшают дистанцию class Graph: ...

Графы: реализация алгоритма Беллмана-Форда
Написать программу, реализующую алгоритм Беллмана-Форда.

Восстановление пути из алгоритма Форда-Беллмана
Реализовал алгоритм Форда-Беллмана, но не получается правильно восстановить пути, подскажите, где ошибаюсь. #define...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
dev-c++5.11 Продолжаю движение.
russiannick 08.06.2025
Казалось, день прошел впустую. Просмотрел кучу видео и только потом заметил заголовок - уроки си. Искусители сбивали новичка с пути с++. Так легко ошибиться когда вокруг столько яп содержащих в. . .
Квантовые алгоритмы и обработка строк в Q#
EggHead 07.06.2025
Квантовые вычисления перевернули наше представление о том, как работать с данными, а Q# стал одним из ключевых языков для разработки квантовых алгоритмов. В традиционых системах мы оперируем битами —. . .
NUnit и C#
UnmanagedCoder 07.06.2025
В . NET существует несколько фреймворков для тестирования: MSTest (встроенный в Visual Studio), xUnit. net (более новый фреймворк) и, собственно, NUnit. Каждый имеет свои преимущества, но NUnit. . .
с++ Что нового?
russiannick 06.06.2025
Продолжаю обзор dev-cpp5. 11. Посмотрев на проекты, предоставленные нам для обучения, становится видно, что они разные по содержащимся файлам где: . dev обязательно присутствует . cpp/ . c один из них. . .
WebAssembly в Kubernetes
Mr. Docker 06.06.2025
WebAssembly изначально разрабатывался как бинарный формат инструкций для виртуальной машины, обеспечивающий высокую производительность в браузерах. Но потенциал технологии оказался гораздо шире - она. . .
Как создать первый микросервис на C# с ASP.NET Core, step by step
stackOverflow 06.06.2025
Если говорить простыми словами, микросервисная архитектура — это подход к разработке, при котором приложение строится как набор небольших, слабо связанных сервисов, каждый из которых отвечает за. . .
Рисование коллайдеров Box2D v2 на Three.js с помощью порта @box2d/core
8Observer8 06.06.2025
Используется порт Box2D v2 под названием @box2d/ core - пакет NPM. Загрузил документацию Box2D v2 на Netlify: https:/ / box2d-v2-docs. netlify. app/ Документацию Box2D v2 можно скачать с официального. . .
Как создать стек в Python
AI_Generated 05.06.2025
Как архитектор с более чем десятилетним опытом работы с Python, я неоднократно убеждался, что знание низкоуровневых механизмов работы стеков дает конкурентное преимущество при решении сложных задач. . . .
Server-Sent Events (SSE) в Node.js
run.dev 05.06.2025
Потоковая передача данных с сервера прямо в браузер стала повседневной потребностью - от биржевых графиков и спортивных трансляций до чатов и умных дашбордов. Много лет разработчики полагались на. . .
Создаем RESTful API на Golang с Fiber
golander 04.06.2025
Я перепробовал десятки фреймворков для создания RESTful API за последние годы, и когда впервые столкнулся с Fiber, понял, что это совсем другой уровень. Нет, я не собираюсь рассказывать сказки о. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
OSZAR »