Грокаем а Иллюстрированное пособие для программистов и любопытствующих

ПАРК



олучит постер менее чем за $0? Продолжайте читать, когда будете готовы ответить на вопрос. Правильный ответ: нет, не удастся. Так как постер явля­ется узлом с наименьшей стоимостью, до которого может добраться Рама, снизить его стоимость невозможно. На происходящее можно взглянуть иначе: предположим, вы едете из дома на работу.
Если вы выберете путь к школе, это займет 2 минуты. Если вы выберете путь к парку, это займет 6 минут. Существует ли путь, при котором вы вы­бираете путь к парку и оказываетесь в школе менее чем за 2 минуты? Это невозможно, потому что только для того, чтобы попасть в парк, потребует­ся более 2 минут. С другой стороны, можно ли найти более быстрый путь в парк? Да, можно.
Э
ЭТОТ ПУТЬ ЗАНИМАЕТ 6 МИН \


ПАРК

^ РАБОТА

ШКОЛА
ТОТ ПУТЬ ЗАНИМАЕТ ВСЕГО 3 МИН
В этом заключается ключевая идея алгоритма Дейкстры: в графе ищется путь с наименьшей стоимостью. Пути к этому узлу с меньшими затратами не существует!
Возвращаемся к музыкальному примеру. Вариант с постером обладает наи­меньшей стоимостью.
Шаг 2: Вычислить, сколько времени потребуется для того, чтобы добраться до всех его соседей (стоимость).

стои-

РОДИТЕЛЬ	УЗЕЛ	МОСТЬ
КНИГА		!Г
КНИГА	ПОСТЕР	0
РРСТЁРС		«Мез**. -
•ДОСТЕР ;	БАРАБАН
■	ПИАНИНО	СО

С
БЛС—

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

"книга	ПЛАСТИНКА	S _
"книга	ПОСТЕР	р
ПОСТЕР	ГИТАРА
ПОСТЕР	БАРАБАН	3S
—	ПИАНИНО	©О

к: этим УЗЛАМ ПЕРЕХОДИМ ОТ УЗЛА «ПОСТЕР»


РОДИТЕЛЬ УЗЕЛ


стои­
мость



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

стой-

РОДИТЕЛЬ	УЗЕЛ	МОСТЬ
КНИГА	ПЛАСТИНКА	5
КНИГА	ПОСТЕР	0
-ПЛЛ'СТЙНКА - • : *^N'' • ^ч	ГИТАРА	0-2 0:
ДЛАСТИНКV	БАРАБАН	#:25-
—	ПИАНИНО	оо

Смотрите, стоимости барабана и гитары обновились! Это означает, что к барабану и гитаре дешевле перейти через ребро, идущее от пластинки. Соответственно, пластинка назначается новым родителем обоих инстру­ментов.

Следующий по стоимости узел — бас-гитара. Обновите данные его со­седей.

стои-

РОДИТЕЛЬ	УЗЕЛ	ЛЛОСТЬ
КНИГА		S’
КНИГА		0
ПЛАСТИНКА		20
ПЛАСТИНКА		25
ГИТАРА L.		74-0Э

Х
орошо, мы наконец-то вычислили стоимость для пианино при условии обмена гитары на пианино. Соответственно, гитара назначается родителем. Наконец, задается стоимость последнего узла — барабана.

стои-

РОДИТЕЛЬ	УЗЕЛ	МОСТЬ
КНИГА	ПЛАСТИНКА	5"
КНИГА	ПОСТЕР	0
ПЛАСТИНКА	ГИТАРА	20
ПЛАСТИНКА	БАРАБАН	2 Г
БАРАБАН	ПИАНИНО 7	г 35'г

О
казывается, Рама может получить пианино еще дешевле, поменяв удар­ную установку на пианино. Таким образом, самая дешевая цепочка обменов обойдется Раме в $35.
Теперь, как я и обещал, необходимо вычислить итоговый путь. К этому моменту вы уже знаете, что кратчайший путь обойдется в $35, но как этот путь определить? Для начала возьмем родителя узла «пианино».

РОДИТЕЛЬ	УЗЕЛ
КНИГА	ПЛАСТИНКА
КНИГА	ПОСТЕР
ПЛАСТИНКА	ГИТАРА
ПЛАСТИНКА	БАРАБАН
БАРАБАН	ПИАНИНО

В
КНИГА

качестве родителя узла «пианино» указан узел «барабан».
А
ПОСТЕР


БАРАБАН


в качестве родителя узла «барабан» указан узел «пластинка».
Следовательно, Рама обменивает пластинку на барабан. И конечно, в самом начале он меняет книгу на пластинку. Проходя по родительским узлам в об­ратном направлении, мы получаем полный путь.

БАС­ПЛАСТИНКА ГИТАРА

Серия обменов, которую должен сделать Рама, выглядит так:

ПЛАСТИНКА




БАРАБАН ПИАНИНО

До сих пор я использовал термин «кратчайший путь» более или менее буквально, понимая под ним вычисление кратчайшего пути между двумя точками или двумя людьми. Надеюсь, этот пример показал, что кратчайший путь далеко не всегда связывается с физическим расстоянием: он может быть направлен на минимизацию какой-либо характеристики. В нашем примере Рама хотел свести к минимуму свои затраты при обмене. Спасибо Дейкстре!

Ребра с отрицательным весом
В
ПЛАСТИНКА



предыдущем примере Алекс предложил в обмен на книгу один из двух предметов.
П
ПЛАСТИНКА


САРА ДАСТ РАМЕ 47, ЕСЛИ ОН ПОМЕНЯЕТ СВОЮ ПЛАСТИНКУ НА ЕЕ ПОСТЕР


редположим, Сара предложила обменять пла­стинку на постер и при этом она еще и даст Раме $7. Рама ничего не тратит при этом обмене, вместо этого он получит $7. Как изобразить это предло­жение на графе?
Р
ПЛАСТИНКА
ЕСЛИ РАМА ИДЕТ ПО ЭТОМУ ПУТИ, ОН ПОЛУЧАЕТ 40


ПЛАСТИНКА
ЕСЛИ РАМА ИДЕТ ПО ЭТОМУ ПУТИ, ОН ПОЛУЧАЕТ $1

ебро, ведущее от пластинки к постеру, имеет отрицательный вес! Если Рама пойдет на этот обмен, он получит $7. Теперь к постеру можно до­браться двумя способами.
А значит, во втором обмене появляется смысл — Рама получает $2!
Т
ПЛАСТИНКА


КНИГА


ОБЩАЯ СТОИМОСТЬ. 1, - ОБЩАЯ СТОИМОСТЬ ; _фз5 ОБМЕНОВ • *33 .
ОБМЕНОВ '



ПЛАСТИНКА


ПОСТЕР ³ⁱ БАРАБАН


еперь, если вы помните, Рама может обменять постер на барабан. И здесь возможны два пути.
Второй путь обойдется на $2 дешевле, поэтому нужно выбрать этот путь, верно?
И знаете что? Если применить алгоритм Дейкстры к этому графу, Рама выберет неверный путь. Он пойдет по более длинному пути. Алгоритм Дейкстры не может использоваться при наличии ребер, имеющих отри­цательный вес. Такие ребра нарушают работу алгоритма. Посмотрим, что произойдет, если попытаться применить алгоритм Дейкстры к этому графу. Все начинается с построения таблицы стоимостей.

ПЛАСТИНКА	S
ПОСТЕР	0
БАРАБАН

стоимости
Теперь найдем узел с наименьшей стоимостью и обновим стоимости его со­седей. В этом случае постер оказывается узлом с наименьшей стоимостью. Итак, в соответствии с алгоритмом Дейкстры, к постеру невозможно перей­
ти более дешевым способом, чем с оплатой $0 (а вы знаете, что это неверно!) Как бы то ни было, обновим стоимости его соседей.