Информатика | ОГЭ | ЕГЭ | Жизнь, кофе и ЕГЭ по информатике
Без категории · 5 октября 2026 г.
В демо-версии ЕГЭ 2027 появился новый прототип на графы. По сути, это задача на поиск к...
В демо-версии ЕГЭ 2027 появился новый прототип на графы. По сути, это задача на поиск кратчайшего пути от одной вершины графа до другой. Входные данные представлены файлом, в каждой строке которого три числа: целочисленные вершины и дробный вес ребра между этими вершинами. Разберем задачу из демо-версии, для решения используем алгоритм Беллмана-Форда. Да, он медленнее Дейкстры, но зато простой и понятный и работает даже с отрицательными весами. Алгоритм Беллмана-Форда находит в ориентированном графе кратчайшие пути из одной вершины до всех остальных. Алгоритм начинается с инициализации: в самом начале мы задаем расстояние от исходной вершины до самой себя равным нулю, а до всех остальных вершин — бесконечности. Это необходимо для того, чтобы потом производить расчеты, основываясь на этом начальном состоянии. На следующем этапе происходит релаксация ребер графа. Релаксация — это процесс, в котором мы пытаемся обновить расстояние до каждой вершины, сравнивая текущее известное значение с расстоянием до смежной вершины плюс вес ребра, соединяющего их. Если новое значение меньше, чем текущее, мы обновляем его. Для этого мы проходим по всем ребрам графа и применяем эту процедуру. Так как необходимо учесть все возможные пути и их комбинации, данный процесс повторяется (n - 1) раз, где n — это общее количество вершин в графе. После завершения итераций алгоритм проводит еще одну проверку. Мы вновь проходим по всем ребрам и проверяем, можем ли мы снова улучшить расстояния. В результате работы алгоритма мы получаем кратчайшие расстояния от исходной вершины до всех остальных. #информатика #ЕГЭ