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

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

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

Задание

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

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

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

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

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

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

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

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

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

Задание 4. Поиск кратчайшего пути по графу дорог A–E

В задаче дана взвешенная графовая модель дорог между населёнными пунктами A, B, C, D и E, представлена как таблица расстояний между вершинами. Нужно найти кратчайшее расстояние между A и E, передвигаясь только по существующим дорогам и посещая каждый пункт не более один раз. Это проверяет умение работать с графами: распознавать вершины и веса ребер, учитывать симметричность таблицы и строить путь без повторений. Подход к решению начинается с анализа доступных ребер: из A есть дороги в B и C (2 и 3 км), из B в C, D и E (1, 5 и 2 км), из C в A, B и E (3, 1 и 5 км), из D в A, B и E (4, 5 и 7 км), из E в B, C и D (2, 5 и 7 км). Далее следует выбрать маршрут с минимальной суммой расстояний, не повторяя узлы. В зависимости от выбранного пути проверяется кратчайшее расстояние между A и E.