От пыльных серверов до Google Maps: почему мир вернулся к алгоритму Дейкстры

Научное сообщество вновь обратило внимание на алгоритм Эдсгера Дейкстры , изобретённый почти 70 лет назад для поиска кратчайших путей в сети. Этот алгоритм , разработанный голландским учёным в 1956 году, демонстрирует наилучшие результаты даже при самых сложных условиях — например, на запутанных транспортных сетях с интенсивными дорожными потоками. Недавнее исследование доказало, что алгоритм Дейкстры оптимален на любой уличной сети, обеспечивая поиск кратчайшего пути независимо от условий. Эти результаты будут представлены на Симпозиуме по фундаментальным вопросам компьютерных наук в 2024 году, где работа уже отмечена наградой как лучшая статья.

Идея алгоритма появилась у Дейкстры случайно, когда он размышлял о возможностях тогда новой вычислительной машины ARMAC. Суть алгоритма заключается в построении упорядоченного списка времени пути от исходной точки к каждой другой точке сети, что позволяет быстро находить кратчайшие маршруты. Алгоритм Дейкстры работает с графами, где вершины соединены ребрами, представляющими вес, например, время, необходимое для прохождения определённого участка дороги.

В конце жизни Дейкстра объяснил успех своего алгоритма тем, что ему удалось избавиться от лишних сложностей, разработав все детали без использования бумаги и карандаша. Он сосредоточился на минимизации вычислительных затрат, что позволило алгоритму стать основой для многих других исследований. В дальнейшем учёные улучшали его, используя особую структуру данных под названием «куча» для ускорения поиска самой близкой точки.

В 1984 году исследователи создали усовершенствованную версию «кучи», что позволило алгоритму Дейкстры достичь нижней границы времени выполнения, тем самым оптимизировав процесс поиска кратчайших путей. На протяжении следующих почти 40 лет этот алгоритм оставался лучшим решением для задачи кратчайших путей с одного источника.

Недавно исследователи вернулись к вопросу оптимальности алгоритма, пытаясь создать универсально оптимальное решение. Этот подход предполагает нахождение кратчайшего пути в условиях худших возможных дорожных заторов на любых сетях. В 2021 году группа учёных доказала возможность создания универсально оптимальных алгоритмов для некоторых типов графов, но задача поиска кратчайшего пути оставалась нерешённой.

В 2023 году команда молодых исследователей из Цюрихского и Копенгагенского университетов пересмотрела алгоритм Дейкстры с целью адаптировать его к худшим дорожным сценариям. Им удалось разработать более сложный, но универсально оптимальный вариант, способный решать задачи на сетях с отрицательными весами и сложными заторами.

Идея универсально оптимального алгоритма находит применение в различных областях, включая транспорт и логистику. Например, оптимальные алгоритмы могут помогать в планировании маршрутов общественного транспорта, избегая пробок и улучшая мобильность в городах.