Page 164 - Bkhargava_-_Grokaem_algoritmy

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

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

БАС­ стои­
ЛЛАСТИНКА 1~ип~~ r..~ф РО.й.ИТЕ.ЛЬ УJЕ.Л мость
книrА S"
l{HиrA ПОСТЕ.Р ф
книrА : ~9~Т:ЕР.~ l!W-'З!IS.~
·:np~1p': БАРАБАН ~'.ss~-
- ПИАНИНО О<)

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

стои­
рОдМТЕ.ЛЬ УJЕ.Л мость
- книrА ПЛАСТИНКА 5
К 'ЭТИМ YJMM z ПОСТЕ.Р flS
книrА

ПЕ.РЕ.ХОДИМ ОТ ПОСТЕР ГИТАРА зу!J
УJЛА «ПОСТЕР" ПОСТЕР БАРАБАН зs
- ПИАНИНО 00

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

Снова шаг 2: обновляются значения всех его соседей.

стои­
РОДИТЕ.ЛЬ УJЕ.Л мость
ПЛАСТИНКА
l{HиrA ПЛАСТИНКА s
КНИrА ПОСТЕР ф
l{HиrA
~~л.А:с.t~н.к~ ГИПРА '11'/l-'l fij:
' . '
..,.., :nлктинкА: БАРАБАН ;,t: ~s.:
'1 -'1 1 1 " ,"
. ',,, \",, ,"
.: БАРАБАН
·1 - ПИАНИНО С>()
t'~..t
www.trk.kg