РусҚаз

Алгоритм Дейкстры

Информатика · 10 класс · Графы и поиск пути · Урок 3 из 4

Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Что это

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

Водитель такси вечером смотрит на навигатор на приборной панели, за лобовым стеклом огни города и плотный поток машин.

Зачем это нужно

На этой идее держатся навигаторы и службы доставки, маршруты беспилотных автомобилей и дронов, прокладка пакетов данных между серверами в интернете и в дата-центрах. Логистика больших компаний, вроде Амазона, каждый день решает задачи о самых дешёвых маршрутах на огромных графах. ИИ может сгенерировать код за секунду, но нужен человек, который поймёт, что считать весом — время, цену или расход энергии, заметит отрицательный вес, на котором алгоритм сломается, и проверит, что маршрут разумен в жизни. Именно такие люди ставят задачи машинам и отвечают за результат.

Курьерский дрон летит над крышами города на закате, внизу видны улицы и перекрёстки.

Как это работает

У каждой вершины есть метка — лучшее известное расстояние от старта: у старта ноль, у остальных бесконечность. На каждом шаге алгоритм достаёт из очереди вершину с самой маленькой меткой и фиксирует её навсегда. Потом смотрит на её соседей: если через эту вершину до соседа выходит короче, чем было, метку соседа уменьшают. Зафиксированную метку уже ничто не улучшит, ведь любой другой путь идёт через вершины с метками не меньше, а веса не отрицательные. А вот жадный способ — всегда идти по самой дешёвой дороге — подводит: дешёвое ребро в начале может завести на очень дорогой участок в конце.

Путешественник стоит на развилке горных тропинок с картой в руках и сравнивает, какая дорога в итоге окажется короче.

Немного истории

Нидерландский учёный Эдсгер Дейкстра придумал свой алгоритм в тысяча девятьсот пятьдесят шестом году. Позже он рассказывал, что сидел с невестой на террасе кафе в Амстердаме после похода по магазинам и придумал всё минут за двадцать, без карандаша и бумаги. Именно поэтому, по его словам, алгоритм получился таким простым и красивым.

Молодой человек в очках сидит за столиком уличного кафе в Амстердаме середины двадцатого века с чашкой кофе и задумчиво смотрит вдаль, рядом улыбающаяся девушка.

Формула: новая метка

Главное действие алгоритма называется релаксацией ребра. Мы стоим в вершине вэ, до неё уже знаем расстояние, и от неё к соседу у ведёт ребро весом дубль-вэ. Если дэ от вэ плюс дубль-вэ меньше, чем дэ от у, значит, мы нашли дорогу короче, и тогда дэ от у становится равно дэ от вэ плюс дубль-вэ. Здесь дэ — метка, то есть расстояние от старта, а дубль-вэ — вес ребра, и измеряются они в одних единицах, например в минутах. Чем больше вес ребра, тем реже этот переход что-то улучшит, а если ребро совсем лёгкое — метка соседа заметно уменьшится.

  • если d(v) + w < d(u), то d(u) = d(v) + wd(v) — метка вершины v — расстояние от старта, мин
    d(u) — метка соседа u, мин
    w — вес ребра от v к u, мин

Что будем делать на практике

А теперь давай попробуем выполнить практическое задание. Перед тобой граф дорог с вершинами от A до G, на рёбрах написаны минуты в пути; старт в A, финиш в G, у A метка ноль, у всех остальных бесконечность. Ты сам будешь алгоритмом: на каждом шаге нажимай ту вершину, которую алгоритм достанет из очереди, то есть с самой маленькой меткой, и следи, как меняются метки её соседей. Дойди так до финиша, а потом нажми «Жадный» и сравни два маршрута: какой из них быстрее и почему. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.

Задание в опыте

Проведите алгоритм Дейкстры сами: на каждом шаге нажимайте вершину, которую алгоритм достанет из очереди. Дойдите до финиша, а потом нажмите «Жадный» и сравните маршруты.
Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Уроки темы: Графы и поиск пути

  1. Что такое граф
  2. Обход в ширину
  3. Алгоритм Дейкстры
  4. Графы вокруг нас