Page 163 - Bkhargava_-_Grokaem_algoritmy

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

получит постер менее чем за $0? Продолжайте читать, когда будете готовы
ответить на вопрос. Правильный ответ: нет, не удастся. Так как постер явля­
ется узлом с наименъшей стоимостъю, до которого может добратъся Рама,
снизить его стоимость невозможно. На происходящее можно взглянуть
иначе: предположим, вы едете из дома на работу.

f1APK

ШКОЛА

Если вы выберете путь к школе, это займет 2 минуты. Если вы выберете
путь к парку, это займет 6 минут. Существует ли путь , при котором вы вы­
бираете путь к парку и оказываетесь в школе менее чем за 2 минуты? Это
невозможно, потому что только для того, чтобы попасть в парк, потребует­
ся более 2 минут. С другой стороны, можно ли найти более быстрый путь
в парк? Да, можно.

ЭТОТ ПУТЬ ПАРК
JАНИМН.Т
6 мин ), ~
!о~~ .....

ЭТОТ ПУТЬ J
ЗАНИМАЕТ
ВСЕГО
3 мин

В этом заключается ключевая идея алгоритма Дейкстры: в графе ищется
путъ с наименъшей стоимостъю. Пути к этому узлу с менъшими затратами
не существует!

Возвращаемся к музыкальному примеру. Вариант с постером обладает наи­
меньшей стоимостью .

www.trk.kg