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

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

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

Задание

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

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

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

	A	B	C	D	E
A		3	9	8	9
B	3			4
C	9			2	2
D	8	4	2		5
E	9		2	5

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

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

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

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

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

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

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