Когда Эдсгер В. Дейкстра опубликовал свой алгоритм в 1959 году, компьютерные сети почти не существовали. Рассматриваемый алгоритм нашел кратчайший путь между любыми двумя узлами на графе, а вариант усовершенствовал его до поиска кратчайших маршрутов ко всем остальным узлам из одного исходного узла. Это оказалось бы невероятно полезным, поскольку компьютерные сети расширились и превратились в Интернет, который мы все знаем и любим. Об алгоритме многое говорит тот факт, что он до сих пор широко используется в современных сетях и интегрирован в протокол маршрутизации Open Shortest Path First (OSPF), который использует алгоритм Дейкстры Shortest Path First для отображения эффективных маршрутов в сложных сетях.
Несмотря на свою долговечность, у алгоритма есть одна заметная проблема. По сути, алгоритм Дейкстры имеет ограничение по скорости. Предел, известный как барьер сортировки, определяется узким местом обработки, когда алгоритм должен постоянно определять, какая точка находится ближе всего к источнику на любом заданном этапе. Этот непрерывный процесс сортировки ограничивает производительность алгоритма.
Однако теперь новому алгоритму удалось обойти этот барьер и снять последующее ограничение скорости. В статье, опубликованной в 2025 году группой исследователей из Стэнфордского университета и Университета Цинхуа в Пекине, описывается комбинация алгоритма Дейкстры с алгоритмом Беллмана-Форда, позволяющая еще более эффективно вычислять кратчайшие пути. Алгоритм работает, не концентрируясь на отдельных узлах, а, по сути, группируя узлы, что ускоряет поиск за счет уменьшения количества узлов, которые необходимо пройти.
Сетевые алгоритмы: длинный путь к кратчайшему пути
«Сортировочный барьер» в алгоритме Дейкстры на протяжении десятилетий бросал вызов исследователям. К 1984 году исследователи из Принстонского университета усовершенствовали первоначальный алгоритм до такой степени, что был достигнут предел скорости сортировочного барьера. И хотя исследователям удалось преодолеть этот барьер в течение следующих нескольких десятилетий, они основывались на предположениях о «весе» каждого узла (в алгоритме Дейкстры каждому потенциальному узлу присваивается вес; чем меньше узел весит, тем ближе он находится). Поскольку эти методы зависели от допущений, выигрыш в скорости был достигнут за счет точности.
Как ни странно, прорыв произошел, когда исследователи интегрировали в свою работу принципы алгоритма Беллмана-Форда. Алгоритм Беллмана-Форда также используется для вычисления более коротких путей, но он делает это без создания отсортированного списка. Основным недостатком метода Беллмана-Форда является то, что он существенно медленнее алгоритма Дейкстры. Они обнаружили, что использование алгоритма Беллмана-Форда позволяет им выборочно атаковать наиболее влиятельные узлы в сети. Их можно рассматривать как ключевые магистрали, с которыми соединяются многие маршруты. Используя этот метод, алгоритм может более эффективно расширяться и пропускать ненужные вычисления.
Более поздняя доработка удалила аспект рандомизации из процесса и добавила систему уровней, которая организовала поиск более разумно. Результатом стал алгоритм поиска сетевого пути, который наконец преодолел ограничение скорости сортировочного барьера.
Почему чистые алгоритмы все еще имеют значение
Большинство людей слышали о законе Мура — законе, который предсказывает, насколько быстро улучшится производительность оборудования. Первоначально этот закон был основан на удваивании количества транзисторов ежегодно, и хотя впоследствии эта цифра была скорректирована, она до сих пор используется для измерения развития технологий. Однако алгоритмы — невоспетые герои вычислений. Под поверхностью они делают все: от усиления негативных эмоций на таких платформах, как X, до сжатия данных в такие форматы файлов, как JPEG и MP3.
Исследования, проведенные Массачусетским технологическим институтом в 2021 году, показали, что улучшения в алгоритмах часто опережают развитие аппаратного обеспечения. Около 40% алгоритмов соперничали с законом Мура или превосходили его, а четверть улучшилась на порядки больше, чем усовершенствования аппаратного обеспечения.
Этот контекст делает последний прорыв в алгоритме поиска кратчайшего пути еще более примечательным. Тот факт, что алгоритм Дейкстры не улучшился с тех пор, как он достиг своей теоретической максимальной скорости, доказывает, насколько сложной была задача. С 1984 года ученые-компьютерщики считали так называемый барьер сортировки фактическим ограничением скорости для любого алгоритма, основанного на методе сортировки.
Прорыв, сделанный совместной командой Стэнфорда и Университета Цинхуа, доказал, что даже в самых зрелых областях компьютерных технологий еще есть куда совершенствоваться. И хотя это последнее открытие, возможно, не сделает Интернет быстрее в одночасье или чудесным образом не остановит загрузку вашего видео на YouTube, оно напоминает нам о важности алгоритмов — невоспетых героев цифровой эпохи.
