Page 169 - Bkhargava_-_Grokaem_algoritmy

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

А значит, во втором обмене появляется смысл - Рама получает $2!

Теперь, если вы помните, Рама может обменять постер на барабан. И здесь
возможны два пути .

ПЛАСТИНКА ПЛАСТИНКА
c(L

КНИГА

ПОС.ТЕР as ПОСТЕР З!> БАРАБАН
OБ\JlAJI СТОИМОСТЬ. ~~~ -
OБ\J1AJI С.ТОИМОС.ТЬ : $ З5 ОБМЕ.НО6 • , , ,
ОБМЕНОВ

Второй путь обойдется на $2 дешевле, поэтому нужно выбрать этот путь,
верно?

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

ПЛАСТИНКА s

ПОСТЕР >2'

БАРАБАН ~

с.тоимос.ти

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

www.trk.kg