Задание 1 КЕГЭ: дан граф дорог таблицей — как найти длину кратчайшего пути?
В первом задании дают таблицу с длинами дорог между пунктами (часть значений пустые) и схему, где пункты подписаны буквами без привязки к таблице. Надо найти длину кратчайшего пути из A в, например, K. Я каждый раз путаюсь, как сопоставить схему и таблицу. Есть нормальный алгоритм, чтобы не гадать?
2 ответа
Ключ к заданию 1 — степени вершин (сколько дорог из неё выходит). Алгоритм:
- В таблице посчитай для каждой строки/столбца, сколько заполненных ячеек — это число дорог из пункта.
- На схеме посчитай степень каждой вершины (сколько линий из неё выходит).
- Сопоставляй по уникальным степеням: если в таблице ровно один пункт с 4 дорогами и на схеме одна вершина с 4 рёбрами — это одна и та же точка.
- Дальше распутываешь соседей и подписываешь буквы на схеме.
Когда буквы расставлены, кратчайший путь обычно виден глазами или быстрым перебором — пунктов мало (6–8). Сложи длины рёбер по самому короткому маршруту.
Лайфхак: начинай сопоставление с вершины, у которой степень уникальна (например, единственная с 5 дорогами) — от неё разматывается всё остальное.
Добавлю частую ловушку: иногда несколько пунктов имеют одинаковую степень, и однозначно сопоставить сразу нельзя. Тогда смотри на соседей: "вершина степени 3, соединённая с вершиной степени 5" — такая пара обычно уже уникальна. Расставляй буквы парами, а не по одной. И перепроверь: каждая дорога из таблицы должна найтись на схеме, и наоборот, иначе где-то ошибся.