Шаг 50.
Алгоритмы.
Пример поиска кратчайшего пути в графе. Окончание

    На этом шаге завершим рассмотрение примера.

    Теперь необходимо вычислить итоговый путь. К этому моменту вы уже знаете, что кратчайший путь обойдется в 35 тыс. руб., но как этот путь определить? Для начала возьмем родителя узла "пианино" (рис.1).


Рис.1. Таблица

    В качестве родителя узла "пианино" указан узел "барабан" (рис.2).


Рис.2. Граф

    А в качестве родителя узла "барабан" указан узел "пластинка" (рис.3).


Рис.3. Граф

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


Рис.4. Граф

    На следующем шаге рассмотрим пример графа с ребрами, имеющими отрицательный вес.




Предыдущий шаг Содержание Следующий шаг