Задание 4 ОГЭ: как по таблице расстояний найти кратчайший путь между городами?
В задании 4 дают таблицу, где на пересечении строк и столбцов стоят расстояния между пунктами, а где дороги нет — пусто. Надо найти длину кратчайшего пути из A в, например, F. Я просто складываю первые попавшиеся числа и ошибаюсь. Есть нормальный способ?
2 ответа
Главное — не считать по таблице в уме, а нарисовать схему дорог (граф). Это съедает минуту, но почти исключает ошибки.
- Выпиши пункты как точки.
- По таблице соедини линиями те пары, между которыми стоит число, и подпиши длину на линии. Таблица симметрична, поэтому смотри только верхний или нижний треугольник.
- Теперь визуально найди все маршруты из старта в финиш и сложи числа на каждом.
- Выбери наименьшую сумму.
Когда пунктов 6–7, перебор маршрутов руками вполне реален. Ошибка почти всегда от того, что человек путает клетку таблицы — на схеме такого не происходит.
Лайфхак: помечай на схеме рядом с каждым пунктом минимальное расстояние от старта до него, идя по нарастанию. Дошёл до соседа — посчитал сумму, записал, если меньше прежней — обновил. Это, по сути, ручной алгоритм Дейкстры, но в задании 4 пунктов мало, так что хватает и простого перебора маршрутов.