ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ ФОРДА-ФАЛКЕРСОНА ТА ДІНІЦА ДЛЯ ПОШУКУ МАКСИМАЛЬНОГО ПОТОКУ

Тетяна Іванівна Жиленко, Злата Бабич, Вячеслав Штогрін · Наука і техніка сьогодні · 2024

ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ ФОРДА-ФАЛКЕРСОНА ТА ДІНІЦА ДЛЯ ПОШУКУ МАКСИМАЛЬНОГО ПОТОКУ Анотація.Важливою проблемою теорії оптимізаї єстворення мереж зв'язку, транспортних та газотранспортних сполучень, які за короткий час можуть пропустити максимальну кількість ресурсів.Тому у роботі розглянуто проблему знаходження максимального потоку в мережі, відому як "maximum network flow problem", яка виникла на початку двадцятого століття і є актуальною у наш час.У теорії оптимізації та теорії графів проблема побудови мережевих систем і вирішення питання з максимальним потоком виникає постійно.Необхідно знайти такий режим потоку, що забезпечить максимізацію загального потоку у напрямку від джерела до стоку.Для цього було проведено аналіз двох алгоритмів для пошуку максимального потоку в графі: алгоритму Форда-Фалкерсона та алгоритму Дініца.Показано принцип їхньої роботи, а також розглянуті асимптотичні оцінки.Важливими для алгоритма Форда-Фалкерсона є: залишкові мережі, шляхи, які постінно збільшуються та розрізи.Також наведено сім кроків його роботи, які унаочнені графами на кожному кроці.Основною метою роботи алгоритму Форда-Фалкерсона є в знаходження шляху від джерела до стоку, де залишкова пропускна здатність усіх ребер буде додатня.Ці ребра можуть бути пройдені як у прямому, так і в зворотньому напрямку.

Cited by 0 works. doi:10.52058/2786-6025-2023-14(28)-550-561 Open-access PDF

Authors