Page 165 - Bkhargava_-_Grokaem_algoritmy

164 Глава 7. Алгоритм Дейкстры

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

стои­
ПЛАСТИНКА
РОДИТЕЛЬ У.3ЕЛ мость
книrА 5'
книrА 9$
ПЛАСТИНКА LjJ
ПЛАСТИНКА 2S
ГИТАРА :-'4-.~ь :-
ПОСТЕР БАРАБАН

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

стои­
ПЛАСТИНКА РОДИТЕЛЬ У.3ЕЛ мость
книrА ПЛАСТИНКА 5'
книrА ПОСТЕР SZ)
ПЛАСТИНКА гипн 2 $21
книrА
ПЛАСТИНКА БАРАБАН 2 S"
БАРАБАН ПИАНИНО _:-35:..
1 ~ '
ПОСТЕР БАРАБАН

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

www.trk.kg