На этом шаге завершим рассмотрение примера.
Теперь необходимо вычислить итоговый путь. К этому моменту вы уже знаете, что кратчайший путь обойдется в 35 тыс. руб., но как этот путь определить? Для начала возьмем родителя узла "пианино" (рис.1).
Рис.1. Таблица
В качестве родителя узла "пианино" указан узел "барабан" (рис.2).
Рис.2. Граф
А в качестве родителя узла "барабан" указан узел "пластинка" (рис.3).
Рис.3. Граф
Следовательно, ВАся обменивает пластинку на барабан. И конечно, в самом начале он меняет книгу на пластинку (рис.4). Проходя по родительским узлам в обратном направлении, мы получаем полный путь.
Рис.4. Граф
На следующем шаге рассмотрим пример графа с ребрами, имеющими отрицательный вес.
