Автор Все 20 вариантов задания 4 тренажёр ОГЭ-2027 по информатике: кратчайший путь между пунктами по таблице расстояний, путь через пункт и в обход пункта. Условия, решения, ответы.
4 задание тренажёр ОГЭ 2027 по информатике 9 класс
zadanie-4-inf-9-klass-oge-2027В задании 4 ОГЭ по информатике дана таблица дорог между населёнными пунктами с их длиной в километрах. Нужно найти длину кратчайшего пути от одного пункта до другого. Иногда добавляется условие: путь должен пройти через заданный пункт или, наоборот, обойти его.
Задача решается перебором маршрутов, и вся сложность в том, чтобы не пропустить ни одного. Короткая прямая дорога часто проигрывает обходному пути из трёх-четырёх участков, и именно на этом построено большинство вариантов.
Ниже разобраны все 20 вариантов задания 4 из тренировочных вариантов ОГЭ 2027. Сначала о том, как читать таблицу и какие есть способы решения, затем задачи по группам, в конце таблица ответов, типичные ошибки и частые вопросы.
Чтобы найти свою задачу, нажмите Ctrl+F и введите номер варианта или кусок условия, например «проходящего через пункт C» или «не проходящего через пункт D».
Как читать таблицу расстояний
Каждая строка и каждый столбец таблицы соответствуют пункту. Число на пересечении строки B и столбца D — это длина дороги между B и D. Пустая клетка означает, что прямой дороги между пунктами нет. Клетки на диагонали закрашены (в статье они отмечены прочерком): дороги из пункта в самого себя не бывает.
Таблица симметрична относительно диагонали. Число в строке B, столбце D всегда совпадает с числом в строке D, столбце B, ведь это одна и та же дорога. Поэтому достаточно смотреть на одну половину таблицы.
Перед решением полезно выписать дороги для каждого пункта. Например, «D: C — 6, E — 3». Особенно важно сделать это для конечного пункта: в последний пункт можно прийти только по одной из его дорог, и это сразу сужает перебор.
Три способа решения
Перебор маршрутов. Начинаем в стартовом пункте, выписываем все дороги из него, затем все продолжения каждой дороги и так далее, пока не дойдём до конечного пункта. По пути считаем сумму. Получается дерево маршрутов. Ветку можно не продолжать, если её длина уже больше лучшего найденного пути.
Расстановка меток. Для каждого пункта находим кратчайшее расстояние от старта. Сначала стартовому пункту ставим 0, соседям — длины дорог. Затем из пункта с наименьшей меткой пробуем улучшить метки его соседей и повторяем, пока все пункты не будут обработаны. Это упрощённый алгоритм Дейкстры, он особенно удобен, когда пунктов шесть и маршрутов много.
Деление пути пополам. Если путь должен пройти через пункт X, ищем отдельно кратчайший путь от старта до X и от X до финиша, а потом складываем. Важная оговорка: две половины не должны проходить через одни и те же пункты. Если лучшие половины пересекаются, нужно искать другие комбинации. Такая ловушка есть в вариантах 8, 12 и 20.
Если путь не должен проходить через пункт X, проще всего мысленно вычеркнуть из таблицы его строку и столбец и решать обычную задачу на оставшихся дорогах.
Какие задачи встречаются в 20 вариантах
| Тип задачи | Варианты |
|---|---|
| Кратчайший путь между двумя пунктами | 1, 2, 7, 9, 15, 16, 17, 18 |
| Кратчайший путь, проходящий через заданный пункт | 3, 4, 8, 10, 11, 12, 13, 14, 19, 20 |
| Кратчайший путь, не проходящий через заданный пункт | 5, 6 |
Кратчайший путь между двумя пунктами: варианты 1, 2, 7, 9, 15, 16, 17, 18
Вариант 1. Кратчайший путь между A и F, дороги из A: AB = 1, AC = 2, AD = 6, AE = 4, AF = 8
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 1 | 2 | 6 | 4 | 8 |
| B | 1 | — | 3 | |||
| C | 2 | — | 1 | 7 | ||
| D | 6 | 3 | — | 8 | 3 | |
| E | 4 | 1 | 8 | — | ||
| F | 8 | 7 | 3 | — |
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. В F ведут дороги из A (8), C (7) и D (3). Самая короткая — из D, поэтому ищем, как быстрее всего добраться до D.
Напрямую A–D — это 6 км, а через B получается A–B–D = 1 + 3 = 4 км. Тогда A–B–D–F = 4 + 3 = 7.
Сравним с остальными маршрутами: прямая дорога A–F — 8, A–C–F = 2 + 7 = 9, A–D–F = 6 + 3 = 9, A–E–C–F = 4 + 1 + 7 = 12. Короче семи ничего нет.
Ответ: 7.
Вариант 2. Кратчайший путь между A и F, дороги из A: AB = 2, AD = 7, AF = 12
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 2 | 7 | 12 | ||
| B | 2 | — | 1 | 3 | 9 | |
| C | 1 | — | 1 | |||
| D | 7 | 3 | 1 | — | 3 | 5 |
| E | 3 | — | 4 | |||
| F | 12 | 9 | 5 | 4 | — |
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. Прямая дорога A–F длиной 12 км заметно длиннее обходных путей.
Через B: A–B–F = 2 + 9 = 11.
Через D: до D можно добраться тремя способами — напрямую (7), через B (2 + 3 = 5) и через B и C (2 + 1 + 1 = 4). Самый короткий — A–B–C–D, 4 км. Из D в F напрямую 5 км, через E 3 + 4 = 7 км.
Итого A–B–C–D–F = 4 + 5 = 9. Это меньше, чем A–B–D–F = 10 и A–B–F = 11.
Пример хорошо показывает главную идею задания: самый длинный по числу участков маршрут здесь оказался самым коротким по километрам.
Ответ: 9.
Вариант 7. Кратчайший путь между A и D, дороги из A: AB = 3, AD = 8, AE = 6
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | — | 3 | 8 | 6 | |
| B | 3 | — | 1 | 2 | |
| C | 1 | — | 2 | 3 | |
| D | 8 | 2 | — | 4 | |
| E | 6 | 2 | 3 | 4 | — |
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. Прямая дорога A–D — 8 км. Попробуем обходные пути:
- A–B–C–D = 3 + 1 + 2 = 6;
- A–B–E–D = 3 + 2 + 4 = 9;
- A–E–D = 6 + 4 = 10;
- A–E–C–D = 6 + 3 + 2 = 11.
Наименьшая длина 6.
Ответ: 6.
Вариант 9. Кратчайший путь между A и D, дороги из A: AB = 1, AC = 4, AE = 7
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | — | 1 | 4 | 7 | |
| B | 1 | — | 2 | ||
| C | 4 | 2 | — | 6 | 2 |
| D | 6 | — | 3 | ||
| E | 7 | 2 | 3 | — |
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. Прямой дороги из A в D нет. В D можно попасть только из C (6) или из E (3).
Кратчайший путь до C — через B: A–B–C = 1 + 2 = 3 (напрямую 4). До E быстрее всего через C: A–B–C–E = 3 + 2 = 5 (напрямую 7).
Получаем варианты: через C — 3 + 6 = 9, через E — 5 + 3 = 8.
Итого A–B–C–E–D = 1 + 2 + 2 + 3 = 8.
Ответ: 8.
Вариант 15. Кратчайший путь между A и D, дороги из A: AB = 10, AC = 20, AE = 20
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | — | 10 | 20 | 20 | |
| B | 10 | — | 10 | ||
| C | 20 | 10 | — | 9 | 1 |
| D | 9 | — | 7 | ||
| E | 20 | 1 | 7 | — |
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. В D ведут две дороги: из C (9) и из E (7).
До E: напрямую 20, через C 20 + 1 = 21. До C: напрямую 20, через B 10 + 10 = 20.
Маршруты до D:
- A–E–D = 20 + 7 = 27;
- A–C–E–D = 20 + 1 + 7 = 28;
- A–B–C–E–D = 10 + 10 + 1 + 7 = 28;
- A–C–D = 20 + 9 = 29.
Минимум 27. Здесь интересно, что очень короткая дорога C–E длиной 1 км не помогает: чтобы до неё добраться, нужно сначала проехать 20 км до C.
Ответ: 27.
Вариант 16. Кратчайший путь между A и D, дороги из A: AB = 4, AC = 12, AE = 16
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | — | 4 | 12 | 16 | |
| B | 4 | — | 5 | ||
| C | 12 | 5 | — | 16 | 6 |
| D | 16 | — | 7 | ||
| E | 16 | 6 | 7 | — |
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. В D ведут дороги из C (16) и из E (7). Вторая намного короче, поэтому ищем лучший путь до E.
До E: напрямую 16, через C 12 + 6 = 18, через B и C 4 + 5 + 6 = 15.
Значит, A–B–C–E–D = 15 + 7 = 22. Прямой путь через E, A–E–D, на километр длиннее: 23.
Ответ: 22.
Вариант 17. Кратчайший путь между A и B, дороги из A: AC = 8, AD = 3, AE = 19
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | — | 8 | 3 | 19 | |
| B | — | 22 | 11 | ||
| C | 8 | 22 | — | 9 | 10 |
| D | 3 | 9 | — | ||
| E | 19 | 11 | 10 | — |
Определите длину кратчайшего пути между пунктами A и B. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. Прямой дороги A–B нет. В B ведут дороги из C (22) и из E (11).
До E: напрямую 19, через C 8 + 10 = 18. До C: напрямую 8.
Маршруты:
- A–C–E–B = 8 + 10 + 11 = 29;
- A–E–B = 19 + 11 = 30;
- A–C–B = 8 + 22 = 30.
Пункт D здесь тупиковый: из него можно попасть только в A и C, и путь через него получается длиннее.
Ответ: 29.
Вариант 18. Кратчайший путь между A и B, дороги из A: AB = 15, AC = 13, AE = 7
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | — | 15 | 13 | 7 | |
| B | 15 | — | 3 | ||
| C | 13 | 3 | — | 2 | 5 |
| D | 2 | — | 2 | ||
| E | 7 | 5 | 2 | — |
Определите длину кратчайшего пути между пунктами A и B. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. Есть прямая дорога A–B длиной 15 км. Кроме неё, в B ведёт только дорога из C (3 км), поэтому ищем кратчайший путь до C.
До C: напрямую 13, через E 7 + 5 = 12, через E и D 7 + 2 + 2 = 11.
Значит, A–E–D–C–B = 11 + 3 = 14. Это на километр короче прямой дороги.
Ответ: 14.
Путь через заданный пункт: варианты 3, 4, 8, 10, 11, 12, 13, 14, 19, 20
Здесь работает деление пути пополам: ищем кратчайший путь до промежуточного пункта и от него до финиша. Но каждый раз нужно проверять, что половины не используют одни и те же пункты.
Вариант 3. Кратчайший путь между A и F через пункт D, дороги из A: AB = 2, AD = 5, AE = 2
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 2 | 5 | 2 | ||
| B | 2 | — | 2 | 2 | 6 | |
| C | 2 | — | 1 | 3 | ||
| D | 5 | 2 | 1 | — | 2 | 1 |
| E | 2 | 2 | — | 2 | ||
| F | 6 | 3 | 1 | 2 | — |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. Первая половина, от A до D: напрямую 5, через B 2 + 2 = 4, через E 2 + 2 = 4.
Вторая половина, от D до F: прямая дорога длиной 1.
Итого 4 + 1 = 5. Подходят сразу два маршрута: A–B–D–F и A–E–D–F.
Условие «через пункт D» здесь существенно. Без него лучшим был бы путь A–E–F длиной 4 км.
Ответ: 5.
Вариант 4. Кратчайший путь между A и F через пункт C, дороги из A: AB = 3, AD = 2, AE = 6
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 3 | 2 | 6 | ||
| B | 3 | — | 1 | 5 | ||
| C | 1 | — | 3 | 2 | 2 | |
| D | 2 | 3 | — | 2 | ||
| E | 6 | 2 | 2 | — | 3 | |
| F | 5 | 2 | 3 | — |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. От A до C: через B 3 + 1 = 4, через D 2 + 3 = 5, через E 6 + 2 = 8. Лучший вариант A–B–C.
От C до F: напрямую 2.
Итого A–B–C–F = 4 + 2 = 6. Этот же маршрут оказывается и самым коротким вообще, без всяких условий.
Ответ: 6.
Вариант 8. Кратчайший путь между A и D через пункт C, дороги из A: AB = 1, AC = 3, AD = 3
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | — | 1 | 3 | 3 | |
| B | 1 | — | 2 | 2 | |
| C | 3 | 2 | — | 7 | 5 |
| D | 3 | 7 | — | 2 | |
| E | 2 | 5 | 2 | — |
Определите длину кратчайшего пути между пунктами A и D, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. Прямая дорога A–D длиной 3 не годится: путь обязан пройти через C. Нельзя и сначала заехать в D, а потом вернуться: каждый пункт посещается один раз.
От A до C: напрямую 3 или через B 1 + 2 = 3.
От C до D: напрямую 7, через E 5 + 2 = 7, через B и E 2 + 2 + 2 = 6.
Лучшая вторая половина использует пункт B, поэтому первая половина должна обойтись без него: A–C напрямую. Получаем A–C–B–E–D = 3 + 6 = 9.
Если же ехать A–B–C, то B уже занят, и от C до D остаётся только 7 км: всего 10. Это хуже.
Ответ: 9.
Вариант 10. Кратчайший путь между A и D через пункт E, дороги из A: AB = 3, AD = 2, AE = 2
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | — | 3 | 2 | 2 | |
| B | 3 | — | 5 | 2 | |
| C | 5 | — | 1 | 3 | |
| D | 2 | 1 | — | 9 | |
| E | 2 | 2 | 3 | 9 | — |
Определите длину кратчайшего пути между пунктами A и D, проходящего через пункт E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. От A до E: напрямую 2.
От E до D: прямая дорога длиной 9, а через C всего 3 + 1 = 4.
Итого A–E–C–D = 2 + 4 = 6.
Обратите внимание на дорогу E–D: она длинная, 9 км, и почти в любом маршруте её выгоднее объехать.
Ответ: 6.
Вариант 11. Кратчайший путь между A и F через пункт D, дороги из A: AB = 3, AC = 4, AE = 7, AF = 15
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 3 | 4 | 7 | 15 | |
| B | 3 | — | 2 | |||
| C | 4 | 2 | — | 6 | ||
| D | 6 | — | 2 | 3 | ||
| E | 7 | 2 | — | 2 | ||
| F | 15 | 3 | 2 | — |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. В D ведут дороги из C (6), E (2) и F (3).
От A до D: через C 4 + 6 = 10, через B и C 3 + 2 + 6 = 11, через E 7 + 2 = 9.
От D до F: напрямую 3, через E 2 + 2 = 4.
Лучшая комбинация: A–E–D–F = 9 + 3 = 12. Пункт E в ней используется только один раз, так что всё в порядке. Для сравнения: A–C–D–F = 13, A–C–D–E–F = 14.
Ответ: 12.
Вариант 12. Кратчайший путь между A и F через пункт D, дороги из A: AB = 3, AC = 4, AE = 9, AF = 15
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 3 | 4 | 9 | 15 | |
| B | 3 | — | 2 | |||
| C | 4 | 2 | — | 6 | ||
| D | 6 | — | 1 | 3 | ||
| E | 9 | 1 | — | 1 | ||
| F | 15 | 3 | 1 | — |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. Таблица похожа на вариант 11, но числа другие, и ответ получается иначе.
От A до D: через C 4 + 6 = 10, через E 9 + 1 = 10.
От D до F: напрямую 3, через E 1 + 1 = 2.
Если просто сложить лучшие половины, получится 10 + 2 = 12. Но надо проверить, что они не пересекаются. Вторая половина D–E–F использует E, значит, первая должна идти через C: A–C–D–E–F = 4 + 6 + 1 + 1 = 12. Всё сходится.
Другие комбинации длиннее: A–E–D–F = 13, A–C–D–F = 13.
Ответ: 12.
Вариант 13. Кратчайший путь между A и F через пункт C, дороги из A: AB = 6, AC = 10, AD = 5, AF = 19
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 6 | 10 | 5 | 19 | |
| B | 6 | — | 6 | |||
| C | 10 | 6 | — | 4 | 6 | |
| D | 5 | 4 | — | 2 | ||
| E | 2 | — | 2 | |||
| F | 19 | 6 | 2 | — |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. От A до C: напрямую 10, через D 5 + 4 = 9, через B 6 + 6 = 12.
От C до F: напрямую 6, через D и E 4 + 2 + 2 = 8.
Лучшая первая половина A–D–C, после неё D уже занят, и вторая половина — только C–F. Получаем A–D–C–F = 9 + 6 = 15.
Проверим альтернативы: A–C–F = 16, A–C–D–E–F = 18. Ответ 15.
Ответ: 15.
Вариант 14. Кратчайший путь между A и F через пункт C, дороги из A: AB = 3, AC = 10, AD = 5, AF = 19
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 3 | 10 | 5 | 19 | |
| B | 3 | — | 2 | |||
| C | 10 | 2 | — | 2 | 7 | |
| D | 5 | 2 | — | 2 | ||
| E | 2 | — | 2 | |||
| F | 19 | 7 | 2 | — |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. От A до C: через B 3 + 2 = 5, через D 5 + 2 = 7, напрямую 10.
От C до F: напрямую 7, через D и E 2 + 2 + 2 = 6.
Половины A–B–C и C–D–E–F не пересекаются, поэтому их можно сложить: A–B–C–D–E–F = 5 + 6 = 11. Маршрут проходит через все шесть пунктов.
Для сравнения: A–B–C–F = 12, A–D–C–F = 14.
Ответ: 11.
Вариант 19. Кратчайший путь между A и E через пункт C, дороги из A: AB = 3, AC = 7, AD = 4, AE = 18
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | — | 3 | 7 | 4 | 18 |
| B | 3 | — | 3 | ||
| C | 7 | 3 | — | 5 | 12 |
| D | 4 | 5 | — | 6 | |
| E | 18 | 12 | 6 | — |
Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. От A до C: напрямую 7, через B 3 + 3 = 6, через D 4 + 5 = 9.
От C до E: напрямую 12, через D 5 + 6 = 11.
Половины A–B–C и C–D–E не пересекаются: A–B–C–D–E = 6 + 11 = 17.
Другие маршруты: A–B–C–E = 18, A–C–D–E = 18. Без условия «через C» хватило бы A–D–E = 10.
Ответ: 17.
Вариант 20. Кратчайший путь между A и E через пункт C, дороги из A: AC = 25, AD = 5, AE = 5
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | — | 25 | 5 | 5 | |
| B | — | 10 | 15 | ||
| C | 25 | 10 | — | 30 | |
| D | 5 | 15 | 30 | — | 20 |
| E | 5 | 20 | — |
Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. Самый показательный вариант на правило «каждый пункт можно посетить только один раз». В E ведут всего две дороги: из A (5) и из D (20). Прийти в E из A нельзя: A — начало маршрута, и вернуться в него, чтобы потом поехать в E, не разрешено. Значит, последний участок — D–E, 20 км, и пункт D должен стоять в маршруте прямо перед E.
Поэтому до C нужно добраться, не заезжая в D: остаётся только прямая дорога A–C, 25 км.
От C до D: напрямую 30, через B 10 + 15 = 25.
Итого A–C–B–D–E = 25 + 25 + 20 = 70. Маршрут A–C–D–E длиннее: 75.
Короткая дорога A–D длиной 5 км, которая так и просится в ответ, здесь бесполезна: если поехать по ней, D будет занят, и до E потом уже не добраться.
Ответ: 70.
Путь, не проходящий через пункт: варианты 5 и 6
Вычеркните из таблицы строку и столбец запрещённого пункта и решайте обычную задачу на оставшихся дорогах.
Вариант 5. Кратчайший путь между A и F, не проходящий через пункт C, дороги из A: AB = 3, AD = 2, AE = 6
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 3 | 2 | 6 | ||
| B | 3 | — | 1 | 5 | ||
| C | 1 | — | 1 | 2 | 1 | |
| D | 2 | 1 | — | 2 | ||
| E | 6 | 2 | 2 | — | 3 | |
| F | 5 | 1 | 3 | — |
Определите длину кратчайшего пути между пунктами A и F, не проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. Без пункта C остаются дороги A–B (3), A–D (2), A–E (6), B–F (5), D–E (2), E–F (3).
Маршруты от A до F:
- A–B–F = 3 + 5 = 8;
- A–D–E–F = 2 + 2 + 3 = 7;
- A–E–F = 6 + 3 = 9.
Наименьший — 7. Если бы пункт C был разрешён, хватило бы A–D–C–F = 2 + 1 + 1 = 4: условие здесь меняет ответ почти вдвое.
Ответ: 7.
Вариант 6. Кратчайший путь между A и F, не проходящий через пункт D, дороги из A: AB = 2, AD = 3, AE = 4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 2 | 3 | 4 | ||
| B | 2 | — | 2 | 2 | 6 | |
| C | 2 | — | 1 | 3 | ||
| D | 3 | 2 | 1 | — | 2 | 1 |
| E | 4 | 2 | — | 4 | ||
| F | 6 | 3 | 1 | 4 | — |
Определите длину кратчайшего пути между пунктами A и F, не проходящего через пункт D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение. Без пункта D остаются дороги A–B (2), A–E (4), B–C (2), B–F (6), C–F (3), E–F (4).
Маршруты:
- A–B–C–F = 2 + 2 + 3 = 7;
- A–B–F = 2 + 6 = 8;
- A–E–F = 4 + 4 = 8.
Наименьший — 7. С пунктом D ответ был бы 4: A–D–F = 3 + 1.
Ответ: 7.
Ответы на все 20 вариантов задания 4
| Вариант | Ответ | Вариант | Ответ |
|---|---|---|---|
| 1 | 7 | 11 | 12 |
| 2 | 9 | 12 | 12 |
| 3 | 5 | 13 | 15 |
| 4 | 6 | 14 | 11 |
| 5 | 7 | 15 | 27 |
| 6 | 7 | 16 | 22 |
| 7 | 6 | 17 | 29 |
| 8 | 9 | 18 | 14 |
| 9 | 8 | 19 | 17 |
| 10 | 6 | 20 | 70 |
Где чаще всего теряют балл в задании 4
Берут прямую дорогу, не проверив обходные
Прямая дорога между пунктами — не обязательно самая короткая. В вариантах 2, 7 и 18 обходной путь из трёх-четырёх участков выигрывает у прямой дороги. Перед тем как записать ответ, проверьте хотя бы все маршруты через соседей конечного пункта.
Не замечают пустые клетки
Если клетка пустая, дороги нет, даже если пункты кажутся «рядом». В вариантах 9 и 17 прямой дороги к конечному пункту вообще нет, и путь приходится строить через другие пункты.
Складывают пересекающиеся половины
В задачах «через пункт» легко взять лучший путь до промежуточного пункта и лучший путь от него, не заметив, что оба проходят через один и тот же пункт. В варианте 20 такая ошибка даёт 55 вместо 70: самый короткий путь от C до E идёт через A, а A уже стоит в начале маршрута. В вариантах 8 и 12 число совпало бы случайно, только потому, что там есть другой путь той же длины без повторов.
Не обращают внимания на слово «не»
«Не проходящего через пункт» и «проходящего через пункт» отличаются одним словом. В условиях вариантов 5 и 6 оно выделено жирным, но на экзамене его всё равно пропускают.
Перебирают маршруты бессистемно
Если выписывать маршруты как придётся, один обязательно потеряется. Надёжнее действовать по схеме: перечислить дороги, ведущие в конечный пункт, и для каждой найти кратчайший путь до её начала.
Как проверить себя при подготовке
Перебор всех маршрутов легко написать на Python. Ниже программа для варианта 7: дороги записаны словарём, а функция рекурсивно перебирает все пути, не заходя в уже посещённые пункты.
g = {'A': {'B': 3, 'D': 8, 'E': 6},
'B': {'A': 3, 'C': 1, 'E': 2},
'C': {'B': 1, 'D': 2, 'E': 3},
'D': {'A': 8, 'C': 2, 'E': 4},
'E': {'A': 6, 'B': 2, 'C': 3, 'D': 4}}
def best(u, end, seen):
if u == end:
return 0
return min((w + best(v, end, seen | {v})
for v, w in g[u].items() if v not in seen),
default=float('inf'))
print(best('A', 'D', {'A'}))
Программа выведет 6. Чтобы проверить другой вариант, достаточно переписать словарь по таблице и поменять пункты в последней строке.
Вопросы о задании 4 ОГЭ по информатике
Сколько баллов даёт задание 4?
Один балл за верный ответ. Задание входит в первую часть экзамена, ответ — целое число.
Изменится ли задание 4 в ОГЭ по информатике 2027 года?
По проекту демоверсии ФИПИ на 2027 год структура ОГЭ по информатике не меняется: 16 заданий, на работу отводится 150 минут, максимальный первичный балл — 21. Задание 4 по-прежнему проверяет умение находить кратчайший путь по таблице расстояний.
Нужно ли рисовать граф?
Не обязательно, но часто помогает. Нарисуйте пункты кружками и соедините их линиями с подписанными длинами. На рисунке сразу видны тупиковые пункты и обходные пути. Для таблицы на пять-шесть пунктов это занимает меньше минуты.
Зачем условие «каждый пункт можно посетить только один раз»?
В обычной задаче на кратчайший путь оно ни на что не влияет: возвращаться в уже посещённый пункт всегда невыгодно. Зато в задачах «через пункт» это условие становится решающим. В варианте 20 без него подошёл бы маршрут A–C–A–E длиной 25 + 25 + 5 = 55, а с ним ответ — 70.
Что делать, если два маршрута дают одинаковую длину?
Ничего особенного: в ответ записывается длина, а не сам маршрут. В варианте 3, например, два разных пути имеют длину 5, и ответ — просто 5.
Сколько времени закладывать на задание 4?
Обычно 3–5 минут. Если таблица на шесть пунктов и есть условие «через пункт», лучше потратить лишнюю минуту на проверку альтернатив, чем потерять балл.
Смотрите для 9 класса по информатике