Алгоритми розв’язання задачі про максимальний потік у мережі, порівняння та їх застосування

Марухно Т. В. Алгоритми розв’язання задачі про максимальний потік у мережі, порівняння та їх застосування : випускна кваліфікаційна робота бакалавра : 113 Прикладна математика / Марухно Тарас Васильович. – Київ, 2023. – 45 с.

Метою дипломної роботи є дослідження алгоритмів розв’язання задач про максимальний потік, а саме: порівняння часу розв’язання при різних вхідних даних, визначення для яких розмірів умови задачі який алгоритм є швидшим і наскільки.
Досліджено алгоритм Форда-Фалкерсона. Алгоритм Форда-Фалкерсона є найповільнішим алгоритмом розв’язання задачі про максимальний потік серед розглянутих. Його можна застосовувати лише для розв’язання задач дуже малих розмірів на кшталт 11 вершин та 26 ребер, і його швидкість буде меншою лише в 120 разів порівняно з алгоритмом Едмондса-Карпа, який виявився найшвидшим при такому розмірі, але вже при 20 вершинах та 53 ребрах буде в десятки тисяч разів повільнішим ніж алгоритми Дініца та Едмондса-Карпа.
Зроблено висновок що найшвидшими алгоритмами розв’язання задачі про максимальний потік є алгоритми Едмондса-Карпа та Дініца. Алгоритм Едмондса-Карпа варто застосовувати, коли мережі не є великими (приблизно до 20 вершин). Для більших мереж час роботи алгоритму Дініца буде приблизно таким як Едмондса-Карпа, або швидше.


Ключові слова : алгоритм Форда-Фалкерсона, алгоритми Едмондса-Карпа та Дініца, алгоритм Едмондса-Карпа.