ЗАДАЧА ПОШУКУ НАЙКОРОТШОГО ШЛЯХУ: ПОРІВНЯЛЬНИЙ АНАЛІЗ ОСНОВНИХ АЛГОРИТМІВ

Анотація

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