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

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

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

Задание

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

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

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

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

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

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

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

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

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

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

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