4 задание ОГЭ информатика
Кратчайший путь по таблице
1 балл ≈ 3 мин уровень Б Анализ моделей: кратчайший путь по таблице
Задание 4 – дана таблица расстояний между пунктами (весовая матрица графа). Нужно найти длину кратчайшего пути между двумя пунктами, иногда с условием «проходя через пункт C» или «не проходя через E». 1 балл, ответ – число.
Как читать таблицу. На пересечении строки B и столбца C стоит длина дороги B–C. Пустая клетка – дороги нет. Таблица симметрична: B–C = C–B.
Алгоритм
- Нарисуй граф: кружки-пункты и линии-дороги с подписанными длинами. Каждую дорогу рисуй один раз.
- Поставь у начального пункта 0.
- Идя от начала, для каждого пункта запиши наименьшее расстояние, которым до него можно добраться: «расстояние соседа + длина дороги». Если нашёлся путь короче – исправь число.
- Число у конечного пункта – ответ.
Разобранный пример. Дороги: A–B = 3, A–C = 7, B–C = 2, B–D = 6, C–D = 1, C–E = 4, D–E = 2. Найти кратчайший путь из A в E.
| Пункт | Расчёт | Минимум |
|---|---|---|
| A | старт | 0 |
| B | A + 3 | 3 |
| C | min(A + 7, B + 2) = min(7, 5) | 5 |
| D | min(B + 6, C + 1) = min(9, 6) | 6 |
| E | min(C + 4, D + 2) = min(9, 8) | 8 |
Ответ: 8 (путь A–B–C–D–E). Обрати внимание: прямая дорога A–C = 7 длиннее, чем объезд A–B–C = 5.
Если путь должен проходить через пункт X – посчитай отдельно кратчайший путь «старт → X» и «X → финиш» и сложи. Если пункт X запрещён – вычеркни его из графа вместе со всеми его дорогами и решай заново.
Ловушки
- Самая короткая отдельная дорога не значит самый короткий путь – часто выгоден объезд из нескольких коротких дорог.
- Ошибся при перерисовке таблицы – проверь, что дорог на рисунке столько же, сколько заполненных клеток над диагональю.
- Не учёл дополнительное условие («через C», «не через D»).
- Рисуй граф и сразу подписывай длины – вычисления в голове по таблице дают ошибки.
- Пиши у каждой вершины текущий минимум и исправляй его, если нашёлся путь короче.
- Проверь 2–3 «подозрительных» маршрута перебором – это быстро на маленьком графе.
Разобранные задания 4 из открытого банка ФИПИ
Пример 1 · код ФИПИ 672944
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
| A | B | C | D | E | |
| A | 3 | 5 | |||
| B | 3 | 1 | 6 | ||
| C | 5 | 1 | 4 | 1 | |
| D | 6 | 4 | 3 | ||
| E | 1 | 3 |
Определите длину кратчайшего пути между пунктами A и D (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.
Показать ответ и решение
Ответ: 8
Перебираем маршруты из A в D. Самый короткий – A–B–C–D, его длина 8.
Остальные варианты длиннее (проверено полным перебором).
Пример 2 · код ФИПИ B1B889
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
| A | 7 | 4 | |||
| B | 7 | 2 | 5 | ||
| C | 4 | 2 | 4 | ||
| D | 4 | 5 | |||
| E | 5 | 5 |
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Показать ответ и решение
Ответ: 11
Перебираем маршруты из A в E. Самый короткий – A–C–B–E, его длина 11.
Остальные варианты длиннее (проверено полным перебором).
Пример 3 · код ФИПИ 0D2DD9
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
| A | 1 | 2 | 15 | |||
| B | 1 | 3 | 4 | |||
| C | 2 | 3 | 1 | 6 | ||
| D | 4 | 1 | 2 | 6 | ||
| E | 2 | 1 | ||||
| F | 15 | 6 | 6 | 1 |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт С. Передвигаться можно только по дорогам, указанным
в таблице. Каждый пункт можно посетить только один раз.
Показать ответ и решение
Ответ: 6
Перебираем маршруты из A в F через C. Самый короткий – A–C–D–E–F, его длина 6.
Остальные варианты длиннее (проверено полным перебором).
Частые вопросы о задании 4
Сколько баллов даёт задание 4 ОГЭ по информатике?
Максимум – 1 первичный балл. Норма времени на экзамене – около 3 мин. Уровень сложности – Б.
Что проверяет задание 4?
Задание 4 – дана таблица расстояний между пунктами (весовая матрица графа). Нужно найти длину кратчайшего пути между двумя пунктами, иногда с условием «проходя через пункт C» или «не проходя через E». 1 балл, ответ – число.
Как подготовиться к заданию 4?
Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.