Модифікація використання алгоритму Флойда-Уоршелла при роботі з графами деревної структури

Анотація

Невід’ємною частиною будь-якого програмного проекту є використання алгоритмів. Алгоритми, які є канвою, основою великої кількості програмних рішень є класичними, надрукованими у настільних книжках програміста та ще частогусто реалізовані на багатьох мовах програмування. Але будь-який програмний проект має багато тонкощів, які неможливо вичерпати класичним підходом, пошуки вже готових рішень за заданими параметрами також бувають невдалі, або готові функції не відповідають заданим критеріям швидкодїї або точності. Прикладом такого алгоритму, розв’язання якого запропоновано в даній роботі є алгоритм пошуку всіх мінімальних відстаней між будь-якими двома верхівками на графі деревної структури. За основу його написання було використано алгоритм Флойда-Уоршелла, універсальний, створений для графів будь-якої структури, циклічних або орієнтованих. В роботі доведено, що деревна структура графа значно простіша ніж узагальнена циклічна структура, де у якості зв’язків можуть бути ребра або можуть бути дуги. В роботі показано, що у дереві існує лише один шлях між будь якими двома верхівками, тобто ми не маємо жодної необхідності перераховувати отриману відповідь – відстань між двома певними верхівками, сподіваючись, що вона буде більш оптимальною згідно критеріям завдання, отже ми можемо позбутися величезної кількості умовних операторів та зовнішнього циклу, кількість ітерацій якого відповідає кількості верхівок, тобто, якщо у звичайному проекті кількість верхівок графа деревної структури стартує від тисячі верхівок, то використовуючи модифікований алгоритм Флойда спеціально під графи деревної структури, а не розповсюджену, так звану, універсальну версію, можна пришвидшити роботу програмного продукту щонайменше вдвічі. Крім того, графи деревної структури мають ще низку структурних відмінностей, які дозволяють прискорити ще від двох до десяти разів по відношенню до готової к використанню універсальної версії алгоритму. Отже, в роботі розглянута методика пристосування класичного алгоритму до специфічних потреб, якими є неорієнтовані графи деревної структури.