Задание № 4 по информатике: кратчайший путь во взвешенном графе

В задании № 4 дана модель дорог или связей между объектами. Нужно найти длину кратчайшего разрешённого пути и записать число в бланк № 1. Максимум — 1 первичный балл.

Позиция проверяет умение анализировать простую модель объекта, представленную взвешенным графом или таблицей смежности. Вершины обозначают пункты, рёбра — дороги, а числа в ячейках — длины или стоимости переходов. Пустая ячейка означает отсутствие прямой связи, а не нулевой вес.

Граф может быть неориентированным, когда по дороге разрешено двигаться в обе стороны, или ориентированным, когда направление задают стрелки. В условии могут запретить повторно посещать вершины либо проходить через отдельный пункт. Все такие ограничения нужно сохранить при переборе маршрутов.

Кратчайший путь определяют по сумме весов всех его рёбер. Прямая дорога не обязательно выгоднее маршрута с несколькими промежуточными пунктами.

• 1 балл: длина кратчайшего пути записана в требуемой форме и полностью совпадает с эталоном.
• 0 баллов: указана неверная длина, несколько вариантов, маршрут вместо числа или ответ с посторонними символами; ответ отсутствует либо не соответствует инструкции.

За правильный маршрут с ошибкой в сумме и за верную сумму по запрещённому маршруту частичный балл не дают.

1. Перенесите все вершины, связи, направления и веса. Не превращайте пустую ячейку в ребро нулевой длины.
2. Поставьте у начальной вершины расстояние 0, у остальных — бесконечность.
3. Выбирайте непосещённую вершину с наименьшим известным расстоянием.
4. Для каждого разрешённого соседа сравнивайте прежнюю оценку с расстоянием через выбранную вершину и сохраняйте меньшую.
5. Продолжайте, пока конечная вершина не получит окончательное расстояние.
6. Восстановите маршрут по предшественникам и ещё раз сложите веса его рёбер.

Условие. Между пунктами A, B, C, D, E и F проложены двусторонние дороги. Их длины в километрах даны в полной таблице. Знак «—» означает, что прямой дороги нет. Найдите длину кратчайшего пути из A в F. Каждый пункт можно посетить не более одного раза.

Ответ: 15.

Пошаговое решение.

1. Из A получаем первые оценки: B — 4, C — 7, D — 12.
2. Ближайшая непосещённая вершина B имеет расстояние 4. Через неё путь до C сокращается до $4+2=6$, до D — до $4+7=11$, до E впервые получаем 16.
3. Следующей выбираем C с расстоянием 6. Через C оценка D становится $6+3=9$, E — $6+7=13$, F — $6+14=20$.
4. Выбираем D с расстоянием 9. Через D расстояние до E сокращается до $9+2=11$, а до F — до $9+9=18$.
5. Выбираем E с расстоянием 11. Путь до F через E имеет длину $11+4=15$, что меньше прежних 18.

6. Восстанавливаем маршрут: A → B → C → D → E → F. Его длина равна

   $$4+2+3+2+4=15.$$

Все указанные дороги есть в таблице, направление не нарушено, вершины не повторяются.

• Считать пустую ячейку дорогой с нулевым весом.
• Выбирать маршрут с наименьшим числом рёбер, а не с наименьшей суммой.
• Забывать обновить ранее найденное расстояние, когда появился более короткий путь.
• Использовать дорогу в обратную сторону в ориентированном графе.
• Складывать не те веса после правильного выбора вершин.
• Записывать маршрут, когда в ответе требуется только длина.

После вычисления проверьте каждую соседнюю пару восстановленного маршрута по исходной таблице и повторите сложение независимо от черновых оценок.

Формат и оценивание позиции сверены с проектами демоверсии и спецификации ОГЭ-2027 ФИПИ. Проект включает 16 заданий, 150 минут работы и максимум 21 первичный балл; позиция № 4 оценивается в 1 балл. Шкала перевода баллов в отметку для 2027 года не опубликована. Таблица, маршрут и решение созданы FastLearn.