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

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

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

Задание

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

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

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

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

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

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

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

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

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

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

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