Навколо світу за кілька годин: вчені створили унікальний метод прокладання маршрутів.

Алгоритм Дейкстри, розроблений голландським комп'ютерником Едсгером Дейкстрою у 1956 році, залишається основоположним у вирішенні задачі найкоротшого шляху в графах та різних схемах, що передбачають маршрут з точки А до точки Б. Спочатку задуманий для демонстрації можливостей нового комп'ютера, Дейкстра створив його структуру без будь-яких письмових матеріалів менш ніж за 20 хвилин у кафе. Його алгоритм ефективно обчислює найкоротший маршрут від однієї початкової точки до всіх інших пунктів призначення в мережі, пише Quanta Magazine.

Незважаючи на свою простоту та адаптивність, що зробило його основоположною темою в навчанні інформатиці, алгоритм Дейкстри залишав місце для оптимізації структур даних, щоб прискорити виконання різних завдань. З роками з'явилися такі вдосконалення, як "кучі", які підвищували швидкість роботи алгоритму за рахунок швидкого пошуку найближчих вершин. Розробка такої спеціалізованої купи у 1984 році встановила теоретичний стандарт для задач найкоротших шляхів з одним джерелом, зробивши алгоритм неперевершеним у найгірших умовах, зазначалося в дослідженні, опублікованому в arXiv.

Проте дослідників все ще інтригувала можливість знайти алгоритм, оптимальний у всіх сценаріях — концепція, відома як "універсальна оптимальність". В результаті нового наукового прориву команда на чолі з Вацлавом Рожоном та Бернхардом Хойплером розробила універсально оптимальний варіант алгоритму Дейкстри. Ця нова версія ефективно працює в будь-якій схемі мережі за найгірших умов трафіку, використовуючи раніше не використовувану властивість деяких структур купи. Їхнє досягнення, спрощення складних конструкцій, підкреслює потенціал простих алгоритмів для виконання суворих завдань.

Хоча цей оновлений алгоритм, можливо, не знайде негайного практичного застосування через обмеження реального світу, такі як обчислювальні витрати в системах типу Google Maps, він вже надихнув на подальші дослідження в галузі теоретичного проектування алгоритмів, здатних прокладати прості та ефективні шляхи на різних картах. Отримані результати будуть відзначені премією за найкращий доповідь на Симпозіумі з основ комп'ютерних наук 2024 року, що підкреслить їх значущість для розвитку цієї області.