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

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

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

Задание

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

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

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

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

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

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

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

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

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

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

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