Паралельна реалізація алгоритму Едмондса-Карпа

Abstract

Виконана розробка паралельної реалізації алгоритму Едмондса-Карпа для знаходження максимального потоку в мережах. Основна увага приділеная оптимізації алгоритму за допомогою багатопоточності та використання паралельних обчислень. Проведено аналіз предметної області, синтез потокового графа та реалізацію мовою C++ із застосуванням OpenMP. Проведене тестування підтвердило скорочення часу виконання у 1.5-2 рази у порівнянні з послідовною версією. Отримані результати демонструють ефективність паралельного підходу для обробки великих графів, що може бути корисним для оптимізації мережевих алгоритмів та розподілених обчислень. Висновки та результати можуть бути використані у майбутніх дослідженнях в цій галузі.A parallel implementation of the Edmonds-Karp algorithm for finding the maximum flow in networks has been developed. The main attention is paid to the optimisation of the algorithm by means of multithreading and the use of parallel computing. The subject area analysis, flow graph synthesis, and implementation by C++ using OpenMP are performed. The conducted testing confirmed the reduction of execution time by 1.5-2 times compared to the sequential version. The results demonstrate the effectiveness of the parallel approach for processing large graphs, which can be useful for optimising network algorithms and distributed computing. The conclusions and results can be used in future research in this area.