68
правок
Изменения
м
→Альтернативный способ решения
==Альтернативный способ решения==
Задачу так же можно решить [[Обход_в_ширину |поиском в ширину]]. Для этого будем поддерживать массив кратчайший расстояний от начальной до текущей вершины. Обходя графв ширину, будем для каждой вершины обновлять ответы у ее сыновей как минимум из старого значения и пути, проходящего через текущую вершину.
В силу особенности обхода графа, когда происходит обновление сыновей вершины, для нее самой уже найден оптимальный ответ.
