Курсова - Алгоритми пошуку найкоротших шляхів на графах. Мова С++ (ID:1243627)

2.4 Порівняльний аналіз алгоритмів У цьому розділі наведено порівняння трьох основних алгоритмів пошуку найкоротших шляхів у графах: алгоритму Дейкстри, алгоритму Беллмана-Форда та алгоритму Флойда–Воршелла. Аналіз проводиться за кількома критеріями: обчислювальна складність, стійкість до негативних ваг та циклів, а також тип задач, які найкраще вирішуються за допомогою кожного з алгоритмів. В (таблиці 2.4.1) проілюстровано що алгоритм Дейкстри є ефективним за умови невеликої кількості вузлів і відсутності негативних ваг, особливо при використанні бінарної купи або пріоритетної черги. Алгоритм Беллмана-Форда демонструє лінійну залежність від кількості ребер, що робить його придатним для розріджених графів. Натомість алгоритм Флойда–Воршелла є менш ефективним у великих графах, однак дозволяє обчислити найкоротші шляхи між усіма парами вершин одночасно. Таблиця 2.4.1 – Порівняння алгоритмів за часом Дейкстри Беллмана-Форда Флойда-Воршелла Часова складність 〖O(n〗^2) O(ne) 〖O(n〗^3) Просторова складність O(e) O(e) 〖O(n〗^2) На графіку (Рис. 2.4.1) представлено залежність часу виконання алгоритмів від кількості вершин nnn у графі. Зростання складності є найбільш помітним у алгоритму Флойда–Воршелла при великих значеннях n, тоді як Дейкстра та Беллман-Форд демонструють кращу масштабованість залежно від структури графа. Рис. 2.4.1 - Графік з часом на осі y та кількістю вузлів n на осі x Таблиця 2.4.2 – Порівняння алгоритмів за стійкістю Як видно з (таблиці 2.4.2), алгоритм Дейкстри не працює коректно у випадках, коли у графі присутні ребра з негативною вагою. Алгоритм Беллмана-Форда має здатність обробляти такі графи та може виявляти наявність негативних циклів. Флойд–Воршелл також працює з негативними вагами, але не здатен виявити негативні цикли, що може призвести до некоректного результату. Застосування кожного з алгоритмів у реальному світі. [7] У комп’ютерних мережах існує необхідність в алгоритмах маршрутизації. Алгоритми маршрутизації визначають шлях для потоку пакетів даних через мережу, щоб трафік оброблявся ефективно. У такій мережі можна використовувати алгоритм найкоротшого шляху для пошуку маршруту з найменшими витратами. У таких ситуаціях оптимальний шлях від кожного маршрутизатора (в даному випадку маршрутизатори утворюють вузли) до іншого. Тому стає більш ефективним використовувати алгоритм Флойда-Маршалла, ніж алгоритм Дейкстри, щоб знайти шляхи між усіма парами за один раз, а не виконувати ту саму операцію для кожного маршрутизатора.