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

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

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

Задание

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

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

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

	A	B	C	D	E
A		6	1		1
B	6			1
C	1			2	2
D		1	2		1
E	1		2	1

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

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

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

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

Задание 4: дороги между населенными пунктами A..E и кратчайший путь через E

Задание 4: анализ графа дорог между A..E и поиск кратчайшего пути через E

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