Грокаем алгоритмы

Когда вы работаете с алгоритмом Дейкстры, с каждым ребром графа связывается число, называемое весом.

Граф с весами называется взвешенным графом. Граф без весов называется невзвешенным графом.

Для вычисления кратчайшего пути в невзвешенном графе используется поиск в ширину. Кратчайшие пути во взвешенном графе вычисляются по алгоритму Дейкстры. В графах также могут присутствовать циклы:

Это означает, что вы можете начать с некоторого узла, перемещаться по графу, а потом снова оказаться в том же узле. Предположим, вы ищете кратчайший путь в графе, содержащем цикл.

Есть ли смысл в перемещении по циклу? Что ж, вы можете использовать путь без прохождения цикла:

А можете пройти по циклу:

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

Но каждый раз, когда вы проходите по циклу, вы только увеличиваете суммарный вес на 8. Следовательно, путь с обходом цикла никогда не будет кратчайшим.

Наконец, вы еще не забыли наше обсуждение направленных и ненаправленных графов из главы 6?

Само понятие ненаправленного графа означает, что каждый из двух узлов фактически ведет к другому узлу. А это цикл!

В ненаправленном графе каждое новое ребро добавляет еще один цикл. Алгоритм Дейкстры работает только с направленными ациклическими графами, которые нередко обозначаются сокращением DAG (Directed Acyclic Graph).

История одного обмена

Но довольно терминологии, пора рассмотреть конкретный пример! Это Рама. Он хочет выменять свою книгу по музыке на пианино.

«Я тебе дам за книгу вот этот постер, — говорит Алекс. — Это моя любимая группа Destroyer. Или могу дать за книгу редкую пластинку Рика Эстли и еще $5». — «О, я слышала, что на этой пластинке есть отличные песни, — говорит Эми. — Готова отдать за постер или пластинку мою гитару или ударную установку».

«Всю жизнь мечтал играть на гитаре, — восклицает Бетховен. — Слушай, я отдам тебе свое пианино за любую из вещей Эми».

Прекрасно! Рама с небольшими дополнительными тратами может поменять свою книгу на настоящее пианино. Теперь остается понять, как ему потратить наименьшую сумму на цепочке обменов. Изобразим полученные им предложения в виде графа:

Узлы графа — это предметы, на которые может поменяться Рама. Веса ребер представляют сумму доплаты за обмен. Таким образом, Рама может поменять постер на гитару за $30 или же поменять пластинку на гитару за $15. Как Раме вычислить путь от книги до пианино, при котором он потратит наименьшую сумму? На помощь приходит алгоритм Дейкстры! Вспомните, что алгоритм Дейкстры состоит из четырех шагов. В этом примере мы выполним все четыре шага, а в конце будет вычислен итоговый путь.

Прежде чем начинать, необходимо немного подготовиться. Постройте таблицу со стоимостями всех узлов. (Стоимость узла определяет затраты на его достижение.)

Таблица будет обновляться по мере работы алгоритма. Для вычисления итогового пути в таблицу также необходимо добавить столбец «родитель».

Вскоре я покажу, как работает этот столбец. А пока просто запустим алгоритм.

Шаг 1: найти узел с наименьшей стоимостью. В данном случае самый дешевый вариант обмена с доплатой $0 — это постер. Возможно ли получить постер с меньшими затратами? Это очень важный момент, хорошенько подумайте над ним. Удастся ли вам найти серию обменов, при которой Рама получит постер менее чем за $0? Продолжайте читать, когда будете готовы ответить на вопрос. Правильный ответ: нет, не удастся. Так как постер является узлом с наименьшей стоимостью, до которого может добраться Рама, снизить его стоимость невозможно. На происходящее можно взглянуть иначе: предположим, вы едете из дома на работу.

Если вы выберете путь к школе, это займет 2 минуты. Если вы выберете путь к парку, это займет 6 минут. Существует ли путь, при котором вы выбираете путь к парку и оказываетесь в школе менее чем за 2 минуты? Это невозможно, потому что только для того, чтобы попасть в парк, потребуется более 2 минут. С другой стороны, можно ли найти более быстрый путь в парк? Да, можно.

В этом заключается ключевая идея алгоритма Дейкстры: в графе ищется путь с наименьшей стоимостью. Пути к этому узлу с меньшими затратами не существует!

Возвращаемся к музыкальному примеру. Вариант с постером обладает наименьшей стоимостью.

Шаг 2: Вычислить, сколько времени потребуется для того, чтобы добраться до всех его соседей (стоимость).

Стоимости бас-гитары и барабана заносятся в таблицу. Они были заданы при переходе через узел постера, поэтому постер указывается как их родитель. А это означает, что для того, чтобы добраться до бас-гитары, вы проходите по ребру от постера; то же самое происходит с барабаном.

Снова шаг 1: пластинка — следующий по стоимости узел ($5).