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

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

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

Задание

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

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

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

	A	B	C	D	E
A		5	9	6	9
B	5			3
C	9			2	2
D	6	3	2		5
E	9		2	5

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

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

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

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

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

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

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