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

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

ОГЭ информатикаЗадание №4Короткий ответКратчайший путьВзвешенный граф по таблице

Задание

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

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

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

	A	B	C	D	E	F
A		1	2			15
B	1		3	4
C	2	3		1		6
D		4	1		2	6
E				2		1
F	15		6	6	1

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

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

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

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

Задание 4: таблица дорог и кратчайший путь через C в графе

Задание 4. Поиск кратчайшего пути A→F через C по таблице дорог

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