Навигатор в телефоне ищет самый короткий маршрут между двумя точками. В задании 4 ОГЭ ты делаешь то же самое вручную: по таблице расстояний между пунктами находишь длину кратчайшего пути.
Чему научишься. По таблице расстояний между пунктами находить длину кратчайшего пути от одного пункта до другого.
Что нужно знать
Таблица расстояний — это способ задать граф (пункты и дороги между ними). Основы графов есть в курсе «Информатика 5-11»: модели и графы. Здесь разберём приём для задания 4.
Что проверяет задание 4
Дана таблица: на пересечении строки и столбца — длина дороги между двумя пунктами (пусто — прямой дороги нет). Нужно найти длину кратчайшего пути между двумя заданными пунктами. Ответ — число.
Как решать: перебор маршрутов
Прямая дорога не всегда короче! Часто путь через промежуточный пункт короче прямого. Поэтому нужно перебрать все разумные маршруты и выбрать самый короткий.
Таблица дорог (км): Маршруты A → D:
A B C D A-B-D = 3 + 2 = 5
A - 3 1 - A-C-D = 1 + 5 = 6
B 3 - - 2 A-B-C-D = нет дороги B-C
C 1 - - 5
D - 2 5 - Кратчайший = 5 (через B)
Порядок решения. 1) выпиши, какие дороги есть у начального пункта; 2) перебери маршруты до конечного пункта (прямой и через 1-2 промежуточных); 3) сложи длины дорог в каждом маршруте; 4) выбери наименьшую сумму.
Разбор примера
Дороги: A-B=4, A-C=1, C-B=2, B-D=3, C-D=7. Кратчайший путь A → D?
Маршруты: A-B-D = 4+3 = 7; A-C-D = 1+7 = 8; A-C-B-D = 1+2+3 = 6. Кратчайший — 6 (через C и B).
Частые ошибки
- Берут прямую дорогу, не проверив путь через промежуточные пункты — а он бывает короче.
- Пропускают маршрут — перебирай внимательно, по всем соседям.
- Складывают неверно — проверь сумму каждого маршрута.
Проверь себя
Контрольный вопрос. Дороги (км): A-B=3, B-D=2, A-C=1, C-D=5. Найдите длину кратчайшего пути от A до D. Впиши только число.
Подсказка: A-B-D = 3+2 = 5; A-C-D = 1+5 = 6. Кратчайший 5.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Дороги (км): A-B=2, B-C=2, A-C=5. Найдите длину кратчайшего пути от A до C. Впиши только число.
Подсказка: A-B-C = 2+2 = 4 короче прямой A-C = 5.
Онлайн-проверка ответа появится позже
Задание. Дороги (км): A-B=4, A-C=1, C-B=2, B-D=3, C-D=7. Найдите длину кратчайшего пути от A до D. Впиши только число.
Подсказка: A-C-B-D = 1+2+3 = 6.
✅ Готово, если: ты ввёл(а) верный ответ, и онлайн-проверка его приняла.
Онлайн-проверка ответа появится позже
Задание. Дороги (км): A-B=1, B-C=5, A-C=2, C-D=1, B-D=6. Найдите длину кратчайшего пути от A до D. Впиши только число.
Подсказка: A-C-D = 2+1 = 3.
✅ Готово, если: ты ввёл(а) верный ответ, и онлайн-проверка его приняла.
Онлайн-проверка ответа появится позже
Задание. Дороги (км): A-B=2, B-E=4, A-C=3, C-E=2, B-C=1. Найдите длину кратчайшего пути от A до E. Впиши только число.
Подсказка: A-C-E = 3+2 = 5 (и A-B-C-E = 2+1+2 = 5).
✅ Готово, если: ты ввёл(а) верный ответ, и онлайн-проверка его приняла.
Онлайн-проверка ответа появится позже
Задание. Дороги (км): A-B=3, A-C=2, B-D=2, C-D=4, C-B=1. Найдите длину кратчайшего пути от A до D. Впиши только число.
Подсказка: A-B-D = 3+2 = 5 (и A-C-B-D = 2+1+2 = 5).
✅ Готово, если: ты ввёл(а) верный ответ, и онлайн-проверка его приняла.
Онлайн-проверка ответа появится позже
Задание. Дороги (км): A-B=5, A-C=2, C-D=1, D-B=1, B-E=2, D-E=5. Найдите длину кратчайшего пути от A до E. Впиши только число.
Подсказка: A-C-D-B-E = 2+1+1+2 = 6.
✅ Готово, если: ты ввёл(а) верный ответ, и онлайн-проверка его приняла.
Онлайн-проверка ответа появится позже
Задание. Дороги (км): A-B=1, B-C=1, C-D=1, D-E=1, A-E=10, A-C=5, B-E=4. Найдите длину кратчайшего пути от A до E. Впиши только число.
Подсказка: A-B-C-D-E = 1+1+1+1 = 4.
✅ Готово, если: ты ввёл(а) верный ответ, и онлайн-проверка его приняла.
Онлайн-проверка ответа появится позже
Итог
Итог. Таблица расстояний — это граф. Кратчайший путь не всегда прямая дорога: перебери маршруты через промежуточные пункты, сложи длины и выбери наименьшую сумму.
Дальше — банк задач с РешуОГЭ с видеоразборами. Прорешай несколько, пока перебор маршрутов не станет быстрым.
Видео. ▶ Видеоразбор задания 4 (обзор)
Задания для тренировки
Банк задач с РешуОГЭ по заданию 4 (30 шт.). Решай прямо на РешуОГЭ; у части задач есть видеоразбор.
- Задача 3
- Задача 23
- Задача 43
- Задача 63
- Задача 83
- Задача 103
- Задача 123
- Задача 143
- Задача 163
- Задача 203
- Задача 223
- Задача 263
- Задача 283
- Задача 303
- Задача 183
- Задача 243
- Задача 323
- Задача 344
- Задача 364
- Задача 384
- Задача 404
- Задача 424
- Задача 444
- Задача 464
- Задача 484
- Задача 504
- Задача 524
- Задача 544
- Задача 564
- Задача 624
← Назад: задание 3 · ⌂ В начало курса · К навигатору задания 4 →
