Задание 4 ОГЭ: как найти кратчайший путь по схеме дорог?
В задании 4 ОГЭ дают таблицу или схему дорог между городами и спрашивают длину кратчайшего пути из A в B. Как искать кратчайший путь по таблице расстояний, чтобы ничего не пропустить? Есть какой-то надёжный способ?
2 ответа
Задание 4 бывает в двух видах: по таблице смежности или по схеме (рисунку). Способ один — перебрать все пути и выбрать самый короткий.
Алгоритм:
- Если дана таблица — нарисуйте граф: точки (города) и рёбра с числами (расстояния). Это резко снижает число ошибок.
- Выпишите все возможные маршруты из старта в финиш.
- Сложите длины рёбер на каждом маршруте.
- Выберите минимум.
Пример. Пути из A в D:
- A→B→D = 3 + 5 = 8
- A→C→D = 2 + 4 = 6
- A→B→C→D = 3 + 1 + 4 = 8
Кратчайший — A→C→D = 6.
Важно про таблицу: в ней на пересечении строки и столбца стоит длина прямой дороги. Пустая клетка или прочерк = прямой дороги нет, ехать надо через другие города.
Частые ошибки:
- забывают, что граф неориентированный — дорога A→B равна B→A;
- пропускают «обходные» маршруты, которые длиннее по числу городов, но короче по сумме;
- считают по диагонали таблицы (там всегда 0 или пусто — это путь города в себя).
Если городов много (5–6) и путей реально много, рисуйте граф и идите «волной» от старта: помечайте у каждого города минимальное накопленное расстояние, обновляя его, если нашли путь короче. Это упрощённый алгоритм Дейкстры.
Для ОГЭ обычно достаточно аккуратного перебора 3–5 маршрутов — главное не лениться и выписать их все, а не угадывать «на глаз».