Page 161 - Bkhargava_-_Grokaem_algoritmy

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

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

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

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

~~с-

rмпРА

Узлы графа - это предметы, на которые может поменяться Рама. Беса
ребер представляют сумму доплаты за обмен. Таким образом, Рама может
поменять постер на гитару за $30 или же поменять пластинку на гитару

www.trk.kg