Порівняльний аналіз алгоритмів пошуку найкоротшого шляху Класичний Дейкстра проти Duan et al (2025)

Мета роботи: Дослідити ефективність алгоритмів пошуку найкоротшого шляху у зважених графах. Основна ціль — порівняти класичний алгоритм Дейкстри, який є стандартом індустрії, з новітнім підходом, запропонованим у статті Duan et al. (2025), на графах різної розмірності та щільності.

Актуальність: Задачі маршрутизації (GPS, мережеві пакети, логістика) вимагають обробки графів з мільйонами вершин у реальному часі. Перевірка нових теоретичних підходів на практиці дозволяє виявити межі їх застосування.

Технологічний стек:

• Мова: Python 3.10+

• Бібліотеки: heapq (пріоритетні черги), matplotlib (візуалізація), argparse (CLI), networkx (для верифікації результатів).

• Інструменти: Git, GitHub.

---

2. Теоретичні відомості та Дискретна математика

Список суміжності (Adjacency List): Список, де індекс — це вершина, а значення — список кортежів (neighbor, weight).

- _Використання:_ Основна структура для роботи алгоритмів.
    
- _Перевага:_ Оптимальна пам'ять $O(V + E)$, швидка ітерація по сусідах.

2.1. Алгоритм Дейкстри (Оптимізований)

Використовує "жадібний" підхід. Для оптимізації пошуку вершини з мінімальною відстанню ми використали Binary Heap (через модуль heapq).

• Теоретична складність: $O((V + E) \log V)$.

• Принцип: На кожному кроці вибирається невідвідана вершина з найменшою поточною міткою відстані.

2.2. Алгоритм Duan et al. (2025)

Реалізація базується на сучасній науковій статті. Алгоритм пропонує покращену структуру даних для обробки графів з цілочисельними вагами, потенційно наближаючись до лінійного часу в специфічних умовах.

• Особливість: Використання складніших евристик або багаторівневих структур даних (Buckets/Hierarchical structures) для прискорення decrease-key операцій.

---

3. Архітектура та Реалізація (Розподіл ролей)

Команда працювала за принципом модульності. Кожен учасник відповідав за окремий компонент пайплайну.

Учасник	Роль	Деталі реалізації
Матвій	Data Parsing & Graph Core	Розробив модуль зчитування CSV. Реалізував конвертацію "Сирих даних" у Матрицю суміжності. Додав перевірку на орієнтованість графа (directed/undirected flags), що критично для коректної побудови ребер.
Олександр	Classic Algorithms	Реалізував алгоритм Дейкстри. Головна оптимізація — використання heapq замість лінійного пошуку, що прискорило роботу на графах >1000 вершин у 50+ разів.
Анастасія	R&D / Advanced Algorithms	Імплементація статті Duan et al. (2025). Найскладніша частина — адаптація математичної нотації статті у код Python та трансформація графа у формат, специфічний для цього алгоритму.
Максим	Data Generation	Створив генератор випадкових графів (data_generator.py). Параметри: кількість вершин ($N$) та щільність ($Density$). Гарантує зв'язність графа, щоб алгоритми завжди знаходили шлях.
Юліана*	Analytics & Visualization	Звів усе в benchmark.py. Використав argparse для запуску тестів з консолі. Побудував графіки залежності часу виконання від $N$ за допомогою matplotlib.

---

4. Експериментальна частина (Результати)

Ми провели тестування на наборі графів від 100 до 10,000 вершин.

Методологія:

• Кожен тест запускався 10 разів, брався середній час.

• Використано модуль random.py для крос-валідації (порівняння результатів з еталонним networkx або між собою).

Ключові знахідки:

1. Малі графи ($N < 500$): Різниця між алгоритмами несуттєва. Дейкстра іноді швидший через менший overhead (накладні витрати на ініціалізацію структур даних Duan).

2. Розріджені графи (Sparse): На графах з малою кількістю ребер Дейкстра з купою працює надзвичайно ефективно.

3. Великі щільні графи: Алгоритм Duan et al. демонструє кращу масштабованість. На графіку видно, що крива зростання часу для Duan є більш пологою, ніж для класичного Дейкстри.

---

5. Висновки та Враження команди

Робота над проєктом дозволила побачити повний цикл розробки програмного забезпечення: від теорії дискретної математики до візуалізації даних.

Фідбек учасників:

Учасник	Враження
Матвій Піх	"Найважче було обробляти 'биті' дані з CSV. Зрозумів, що матриця суміжності — це просто, але пам'ять їсть нещадно."
Іванченко Юліана	"Оптимізація через heapq — це магія. Код став працювати миттєво там, де раніше 'висів' хвилину."
Корнацький Маусим	"Читати наукові статті 2025 року і перетворювати формули на код — це справжній виклик. Теорія на папері виглядає простіше, ніж реальна імплементація, але коли воно запрацювало — це був кайф."
Власюк Олександр	"Генерувати графи цікаво. Довелося згадати теорію ймовірностей, щоб робити дійсно випадкові, але зв'язні графи."
Настя Широкова	"Matplotlib і argparse — це must have. Спочатку ми просто прінтили цифри, але графіки показали нам ті закономірності, які ми не бачили в тексті."

Загальний висновок:

Ми успішно реалізували обидва алгоритми та підтвердили, що для сучасних задач нові підходи (Duan et al.) мають потенціал перевершити класику, особливо на великих даних.