Что это
Представь, что едешь через город: можно проехать три перекрёстка по пробкам, а можно пять по свободной дороге и успеть раньше. Алгоритм Дейкстры ищет не путь с меньшим числом участков, а путь с наименьшей суммой весов — минут, километров или денег.
Зачем это нужно
На этой идее держатся навигаторы и службы доставки, маршруты беспилотных автомобилей и дронов, прокладка пакетов данных между серверами в интернете и в дата-центрах. Логистика больших компаний, вроде Амазона, каждый день решает задачи о самых дешёвых маршрутах на огромных графах. ИИ может сгенерировать код за секунду, но нужен человек, который поймёт, что считать весом — время, цену или расход энергии, заметит отрицательный вес, на котором алгоритм сломается, и проверит, что маршрут разумен в жизни. Именно такие люди ставят задачи машинам и отвечают за результат.
Как это работает
У каждой вершины есть метка — лучшее известное расстояние от старта: у старта ноль, у остальных бесконечность. На каждом шаге алгоритм достаёт из очереди вершину с самой маленькой меткой и фиксирует её навсегда. Потом смотрит на её соседей: если через эту вершину до соседа выходит короче, чем было, метку соседа уменьшают. Зафиксированную метку уже ничто не улучшит, ведь любой другой путь идёт через вершины с метками не меньше, а веса не отрицательные. А вот жадный способ — всегда идти по самой дешёвой дороге — подводит: дешёвое ребро в начале может завести на очень дорогой участок в конце.
Немного истории
Нидерландский учёный Эдсгер Дейкстра придумал свой алгоритм в тысяча девятьсот пятьдесят шестом году. Позже он рассказывал, что сидел с невестой на террасе кафе в Амстердаме после похода по магазинам и придумал всё минут за двадцать, без карандаша и бумаги. Именно поэтому, по его словам, алгоритм получился таким простым и красивым.
Формула: новая метка
Главное действие алгоритма называется релаксацией ребра. Мы стоим в вершине вэ, до неё уже знаем расстояние, и от неё к соседу у ведёт ребро весом дубль-вэ. Если дэ от вэ плюс дубль-вэ меньше, чем дэ от у, значит, мы нашли дорогу короче, и тогда дэ от у становится равно дэ от вэ плюс дубль-вэ. Здесь дэ — метка, то есть расстояние от старта, а дубль-вэ — вес ребра, и измеряются они в одних единицах, например в минутах. Чем больше вес ребра, тем реже этот переход что-то улучшит, а если ребро совсем лёгкое — метка соседа заметно уменьшится.
если d(v) + w < d(u), то d(u) = d(v) + wd(v) — метка вершины v — расстояние от старта, мин
d(u) — метка соседа u, мин
w — вес ребра от v к u, мин
Что будем делать на практике
А теперь давай попробуем выполнить практическое задание. Перед тобой граф дорог с вершинами от A до G, на рёбрах написаны минуты в пути; старт в A, финиш в G, у A метка ноль, у всех остальных бесконечность. Ты сам будешь алгоритмом: на каждом шаге нажимай ту вершину, которую алгоритм достанет из очереди, то есть с самой маленькой меткой, и следи, как меняются метки её соседей. Дойди так до финиша, а потом нажми «Жадный» и сравни два маршрута: какой из них быстрее и почему. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.