Створений у 1959 році нідерландським комп’ютерним вченим Едсгером Дейкстрою, його алгоритм став одним із фундаментальних відкриттів у сфері обчислювальних мереж. Тоді, коли самі комп’ютерні мережі тільки зароджувалися, алгоритм уже знаходив найкоротший шлях між двома будь-якими вузлами в графі, а його модифікація дозволяла визначити найефективніші маршрути до всіх інших вузлів від єдиного початкового пункту. Ця розробка виявилася надзвичайно корисною з розширенням комп’ютерних мереж, які з часом перетворилися на звичний нам Інтернет. Про значимість алгоритму свідчить той факт, що він і досі широко використовується в сучасних мережах та інтегрований у протокол маршрутизації OSPF (Open Shortest Path First), що застосовує алгоритм Дейкстри для побудови оптимальних маршрутів у складних мережевих системах.
Попри свою довговічність, алгоритм мав одне помітне обмеження. Його ефективність була стримана своєрідною “швидкісною межею”, яку фахівці називали “бар’єром сортування”. Це обмеження виникало через “вузьке місце” в обчислювальному процесі, адже алгоритм мусив безперервно визначати, яка точка є найближчою до джерела на кожному етапі. Такий постійний процес сортування обмежував загальну продуктивність. Проте нині з’явився новий алгоритм, якому вдалося обійти цей бар’єр і, відповідно, зняти згадане обмеження щодо швидкості. У науковій праці за 2025 рік, підготовленій дослідницькою командою зі Стенфордського університету та Університету Цінхуа в Пекіні, описано поєднання алгоритму Дейкстри з алгоритмом Беллмана-Форда. Це об’єднання дає змогу ще ефективніше обчислювати найкоротші шляхи. Суть нового підходу полягає не в концентрації на окремих вузлах, а в їхньому групуванні, що значно прискорює пошук, зменшуючи кількість вузлів, які потрібно перевіряти.
Мережеві алгоритми: тривалий шлях до найкоротшої траєкторії
“Бар’єр сортування” в алгоритмі Дейкстри був справжнім викликом для дослідників протягом багатьох десятиліть. Уже до 1984 року науковці Прінстонського університету покращили початковий алгоритм до тієї межі, де була досягнута швидкість, визначена цим бар’єром. І хоча протягом наступних десятиліть окремим командам вдавалося подолати цю межу, їхні методи ґрунтувалися на припущеннях щодо “ваги” кожного вузла. У алгоритмі Дейкстри кожному потенційному вузлу присвоюється певна вага – чим менша вага вузла, тим ближче він до джерела. Оскільки ці методи залежали від таких припущень, приріст у швидкості досягався ціною втрати точності.
Парадоксально, але прорив стався, коли дослідники інтегрували принципи алгоритму Беллмана-Форда у свою роботу. Алгоритм Беллмана-Форда також застосовується для обчислення коротших шляхів, але він робить це, не створюючи відсортованого списку. Головний недолік цього методу – він значно повільніший за алгоритм Дейкстри. Однак, використовуючи алгоритм Беллмана-Форда вибірково, вчені виявили, що можуть орієнтуватися на найбільш впливові вузли в мережі. Їх можна уявити як основні магістралі, до яких приєднується безліч інших маршрутів. Завдяки такому підходу, алгоритм міг ефективніше поширюватися назовні, уникаючи зайвих обчислень. Пізніша доробка дозволила усунути елемент випадковості з процесу та додала систему шарування, яка впорядкувала пошук більш осмислено. Результатом став алгоритм пошуку шляху в мережі, що нарешті подолав “швидкісну межу” бар’єру сортування.
Чому базові алгоритми досі мають вагоме значення
Більшість людей, ймовірно, чули про закон Мура – правило, що передбачає темпи покращення продуктивності апаратного забезпечення. Цей закон спочатку ґрунтувався на щорічному подвоєнні кількості транзисторів, і хоча ця цифра згодом була скоригована, він досі слугує орієнтиром для вимірювання технологічного прогресу. Однак алгоритми – це справжні, хоча й не оспівані, герої обчислювальної техніки. Непомітно для користувача вони виконують безліч завдань – від посилення емоційних реакцій на платформах, як-от X, до стиснення даних у таких форматах, як JPEG і MP3.
Дослідження, проведене Массачусетським технологічним інститутом (MIT) у 2021 році, виявило, що вдосконалення алгоритмів часто випереджає прогрес в апаратному забезпеченні. Приблизно 40% алгоритмів не лише не поступалися, а й перевершували закон Мура за темпами покращення, тоді як чверть з них поліпшувалася на порядки швидше, ніж апаратні компоненти.
Цей контекст робить останній прорив в алгоритмі найкоротшого шляху ще більш видатним. Той факт, що алгоритм Дейкстри не покращувався відтоді, як досяг своєї теоретичної максимальної швидкості, доводить, наскільки складним було це завдання. З 1984 року комп’ютерні вчені вважали так званий “бар’єр сортування” де-факто швидкісною межею для будь-якого алгоритму, що ґрунтується на методі сортування.
Прорив, здійснений об’єднаною командою зі Стенфорда та Університету Цінхуа, довів, що навіть найзріліші галузі обчислювальної техніки все ще мають значний потенціал для вдосконалення. І хоча це новітнє відкриття, можливо, не зробить інтернет швидшим миттєво або не зупинить чудесним чином тривале завантаження вашого відео на YouTube, воно все ж нагадує нам про надзвичайну важливість алгоритмів – цих невидимих, але фундаментальних рушіїв цифрової епохи.
