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

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

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

Задание

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

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

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

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

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

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

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

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

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

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

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