А что, если бы дороги могли быть негативными?

Задача поиска кратчайшего пути от одного источника (SSSP) — одна из старейших, важнейших и наиболее изученных задач в информатике. Большинство из нас ежедневно сталкиваются с задачами поиска кратчайшего пути — например, когда мы используем картографические приложения для навигации на работу или к другу, за кулисами работает алгоритм, эффективно вычисляющий самый быстрый маршрут. Однако, помимо очевидных применений, многие другие типы задач также могут быть представлены как задача поиска кратчайшего пути. Фундаментальная структура данных, лежащая в основе всех этих задач, известна как «граф», который состоит из «узлов» и «ребер» между узлами (например, местоположения и дороги в Google Maps), где каждое ребро имеет число, называемое «весом», часто обозначающее некоторую стоимость, связанную с перемещением по ребру. Во многих случаях веса являются строго неотрицательными числами — например, в Google Maps каждая дорога требует положительного времени для проезда. Но, что интересно, существует также множество задач, в которых веса могут быть как положительными, так и отрицательными. Эффективный алгоритм для неотрицательной версии задачи SSSP существует с 1950-х годов — он известен как алгоритм Дейкстры, знаменитый своей простотой и являющийся излюбленной темой многих курсов по алгоритмам. Также известен (и прост) алгоритм Беллмана-Форда, который решает отрицательную версию задачи SSSP и также существует с 1950-х годов. Однако алгоритм Беллмана-Форда намного медленнее, чем алгоритм Дейкстры. С момента его изобретения было разработано множество алгоритмов для отрицательной версии задачи SSSP, которые достигают всё более высоких скоростей по сравнению с алгоритмом Беллмана-Форда. Но только в 2022 году исследователям наконец удалось добиться «почти линейного времени» выполнения, технический термин, который по сути означает «теоретически, почти так же быстро, как алгоритм Дейкстры». Алгоритм BNW (названный в честь его авторов: Бернштейна, Нанонгкая и Вульфа-Нильсена) достиг этой цели — и, что интересно, их методы полностью отклонились от передовых методов, разрабатываемых в 2020-х годах для решения подобных задач. Вместо этого, их методы больше напоминают методы, используемые в таких алгоритмах, как алгоритм Дейкстры и алгоритм Беллмана-Форда, которые значительно проще. В этом видео мы объясняем, как работает алгоритм BNW, и наиболее важные моменты, которые делают его эффективным. Кроме того, мы рассматриваем вопрос о том, возможно ли применение более простых методов к другим открытым проблемам в алгоритмах обработки графов, и могут ли подобные алгоритмы быть пригодны для практической реализации. Особая благодарность профессору Аарону Бернштейну и профессору Данупону Нанонгкаю за их вклад в создание этого видео, Кристиану Вульф-Нильсену за его участие в проекте и Нью-Йоркскому университету за предоставление финансирования для видео. Как всегда, особая благодарность моим подписчикам на Patreon за помощь в финансировании этого видео. Если вы хотите поддержать этот канал, это один из лучших способов сделать это! Каждый вклад искренне и высоко ценится. Присоединяйтесь здесь:   / purplemindcreations   Это видео является частью «Forefront», коллекции видеороликов на этом канале, посвященных передовым исследованиям в области математики и информатики. Полный плейлист здесь:    • Forefront   Если вы или ваша организация заинтересованы в спонсировании темы будущего видео PurpleMind, пожалуйста, свяжитесь со мной по адресу purplemindcs@gmail.com! Ссылки: Алгоритм BNW: https://arxiv.org/pdf/2203.03456 Другой алгоритм 2022 года: https://arxiv.org/pdf/2203.00671 Структура масштабирования Голдберга: https://epubs.siam.org/doi/10.1137/S0... Первое улучшение времени выполнения BNW: https://arxiv.org/pdf/2304.05279 Еще одно улучшение времени выполнения BNW: https://arxiv.org/pdf/2510.22721 Практическая реализация на основе алгоритма Брингмана и др.: https://drops.dagstuhl.de/entities/do... Улучшение 2025 года для неотрицательных чисел SSSP: https://arxiv.org/pdf/2504.17033 Небольшое замечание о LDD: Хотя в видео это не обсуждается, LDD работает только с неотрицательными графами. В алгоритме BNW LDD выполняется на копии графа, где все отрицательные веса обнуляются, а полученные компоненты используются для исходного графа. Подробнее о LDD можно узнать здесь: https://arxiv.org/pdf/2203.03456 (раздел 6) Музыка Brittle Rille - Reunited Кевина Маклеода распространяется по лицензии Creative Commons Attribution 4.0. https://creativecommons.org/licenses/... Музыка We Always Thought the Future Would Be Kind of Fun Криса Забриски распространяется по лицензии Creative Commons Attribution 4.0. https://creativecommons.org/licenses/... Математические анимации созданы с помощью Manim, автор 3Blue1Brown. Сервер Discord:   / discord  . Присоединяйтесь! По вопросам сотрудничества: purple...