Page 167 - Bkhargava_-_Grokaem_algoritmy

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

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

Б~С­
rИП Р~

!(НИП

nосп.Р

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

~@

nЛКТМНКА

ПМСТМНКА

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

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

www.trk.kg