ФИПИ ОГЭ информатика, задание 4 (0C31A2)

Задание 4: Задача по информатике ОГЭ: найти минимальную сумму дорог между пунктами A и C в данными таблице весов дорог, с условием посещения узлов без повторов.

ОГЭ информатикаЗадание №4Короткий ответКратчайший путь

Задание

№4 · Модели объектов

Впишите правильный ответ.

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

	A	B	C	D	E
A		2		4
B	2		3	5	2
C		3			3
D	4	5			5
E		2	3	5

Определите длину кратчайшего пути между пунктами A и C . Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Подсказка AI-репетитора

Подсказки открываются по одной и не показывают готовый ответ.

Показано 0 из 3

Задание 4: кратчайший путь между A и C по таблице дорог

Задание 4: анализ графа дорог и поиск кратчайшего пути A → C

В задаче требуется определить длину кратчайшего маршрута между пунктами A и C на основе данных таблицы весов дорог между городами A, B, C, D, E. Поскольку маршрут должен проходить только по существующим дорогам и каждый населённый пункт можно посетить один раз, нужно рассмотреть только простые пути без повторения вершин и суммировать их веса. Подход к решению: запишите трекинг путей по графу, используйте симметричность таблицы весов, исключите недоступные или дублирующиеся маршруты, затем найдите минимальную итоговую длину. Такой подход развивает навыки работы с графами, анализа таблиц дорог и наглядного сравнения вариантов пути.