На этом шаге рассмотрим второй шаг алгоритма Дейкстры для решения поставленной задачи.
Шаг 2: вычислить, сколько времени потребуется для того, чтобы добраться до всех соседей вершины (стоимость).
Стоимости гитары и барабана заносятся в таблицу (рис.1).
Рис.1. Таблица
Они были заданы при переходе через узел постера, поэтому постер указывается как их родитель. А это означает, что для того, чтобы добраться до гитары, вы проходите по ребру от постера; то же самое происходит с барабаном (рис. 2).
Рис.2. Измененная таблица
Снова шаг 1: пластинка - следующий по стоимости узел (5 тыс.руб.).
Снова шаг 2: обновляются значения всех его соседей (рис.3).
Рис.3. Измененная таблица
Стоимости барабана и гитары обновились. Это означает, что к барабану и гитаре дешевле перейти через ребро, идущее от пластинки. Соответственно, пластинка назначается новым родителем обоих инструментов.
Следующий по стоимости узел - гитара. Обновите данные его соседей. (рис. 4).
Рис.4. Измененная таблица
Мы вычислили стоимость для пианино при условии обмена гитары на пианино. Соответственно, гитара назначается родителем. Наконец, задается стоимость последнего узла - барабана (рис.5).
Рис.5. Измененная таблица
Оказывается, Вася может получить пианино еще дешевле, поменяв ударную установку на пианино. Таким образом, самая дешевая цепочка обменов обойдется Васе в 35 тыс. рублей.
На следующем шаге закончим рассматривать алгоритм Дейкстры для поставленной задачи.
