Остання редакція: 2025-02-04
Анотація
Виконана розробка паралельної реалізації алгоритму Едмондса-Карпа для знаходження максимального потоку в мережах. Основна увага приділеная оптимізації алгоритму за допомогою багатопоточності та використання паралельних обчислень. Проведено аналіз предметної області, синтез потокового графа та реалізацію мовою C++ із застосуванням OpenMP. Проведене тестування підтвердило скорочення часу виконання у 1.5-2 рази у порівнянні з послідовною версією. Отримані результати демонструють ефективність паралельного підходу для обробки великих графів, що може бути корисним для оптимізації мережевих алгоритмів та розподілених обчислень. Висновки та результати можуть бути використані у майбутніх дослідженнях в цій галузі.
Ключові слова
Посилання
1.Процеси і потоки. Багатозадачність і багатопоточність. Проблеми розробки додатків для багатопотокового середовища. URL: http://um.co.ua/8/8-2/8-228807.html.
2.Maximum flow - Ford-Fulkerson and Edmonds-Karp. URL: https://cp-algorithms.com/graph/edmonds_karp.html.
3. DSA Edmonds-Karp Algorithm. URL: https://www.w3schools.com/dsa/dsa_algo_graphs_edmondskarp.php.
4. Network Flow: Edmonds-Karp Algorithm. URL: https://www.baeldung.com/cs/network-flow-edmonds-karp-algorithm.
5. Modeling the Parallelization of the Edmonds-Karp AlgorithmandApplication.Computer and Information Science; Vol. 12, No. 3; 2019. URL: https://doi.org/10.5539/cis.v12n3p81.
6. MPI для C++. URL: https://www.paulnorvig.com/guides/using-mpi-with-c.html