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

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

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

Задание

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

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

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

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

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

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

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

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

Задание 4: таблица дорог и поиск кратчайшего пути между B и D

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

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