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

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

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

Задание

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

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

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

	A	B	C	D	E	F
A		3	7			2
B	3
C	7			3	1
D			3		1	2
E			1	1
F	2			2

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

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

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

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

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

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

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