На этом шаге рассмотрим первый шаг алгоритма Дейкстры для решения поставленной задачи.
Шаг 1: найти узел с наименьшей стоимостью.
В данном случае самый дешевый вариант обмена с доплатой 0 рублей - это постер. Возможно ли получить постер с меньшими затратами? Это очень важный момент, хорошенько подумайте над ним. Удастся ли вам найти серию обменов, при которой Вася получит постер менее чем за 0 рублей? Правильный ответ: нет, не удастся. Так как постер является узлом с наименъшей стоимостъю, до которого может добратъся Вася, снизить его стоимость невозможно.
На происходящее можно взглянуть иначе: предположим, вы едете из дома на работу (рис.1).
Рис.1. Еще один граф
Если вы выберете путь к школе, это займет 2 минуты. Если вы выберете путь к парку, это займет 6 минут.
Существует ли путь, при котором вы выбираете путь к парку и оказываетесь в школе менее чем за 2 минуты?
Это невозможно , потому что только для того, чтобы попасть в парк, потребуется более 2 минут.
С другой стороны, можно ли найти более быстрый путь в парк? Да, можно (рис.2).
Рис.2. Путь в парк
В этом заключается ключевая идея алгоритма Дейкстры: в графе ищется путъ с наименъшей стоимостъю. Пути к этому узлу с менъшими затратами не существует!
Возвращаемся к музыкальному примеру. Вариант с постером обладает наименьшей стоимостью.
На следующем шаге продолжим рассматривать работу алгоритма Дейкстры на примере.
