Алгоритм Дейкстры Этот алгоритм был создан учёным из Нидерландов по имени Эдсгер Дейкстр в 1959 году. Он находит наименьший путь от начальной точки графа до конечной. График работает только если граф без рёбер и имеет отрицательный вес. Алгоритм часто применяеться в программировании и других сферах информационных технологиях (в протоколах маршрутизации (OSPF(динамический маршрутизатор) и IS-IS(маршрутизатор промежуточной системы)). Пример задачи. Её решение и объяснение Пускай необходимо отыскать самые короткие дистанции с 1-й вершины в плоть до абсолютно всех других...

Несложная задача про написание обхода в ширину, на которой можно потренировать и применить несколько трюков. Читаем условие: В этой задаче нужно построить кратчайший путь, поэтому это явно поиск в ширину или BFS. Этот алгоритм подробно разбирали при решении Задачи 127. Путь. Если вы с ним не знакомы, то рекомендую сначала прочитать тот разбор. По условию задачи, поле очень маленькое (помним, что алгоритм BFS работает за линейное время от количества вершин и рёбер в графе, то есть O(V + E)). Поэтому,...