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

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

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

Задание

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

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

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

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

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

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

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

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

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

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

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