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

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

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

Задание

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

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

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

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

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

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

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

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

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

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

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